{"id":6119,"date":"2021-12-27T10:37:12","date_gmt":"2021-12-27T10:37:12","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=6119"},"modified":"2022-08-22T08:03:52","modified_gmt":"2022-08-22T08:03:52","slug":"aman-string","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/aman-string\/","title":{"rendered":"Aman String"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Find the total number of pairs of indexes (i , j<\/b>) such as subString(i , j<\/b>) contains aman<\/B> atleast once.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\namanaaamanc\n\nOutput:\n20\n\nExplanation:\nSubstrings containing \"aman\" atleast once in it starts at given indexes (1,4), (1, 5), (1, 6), (1, 7), (1, 8), (1,9), (1, 10), (1, 11), (2,10), (2,11), (3,10), (3,11), (4,10), (4,11), (5,10), (5,11), (6,10), (6,11), (7,10), and (7,11). So, total 20 substrings are found.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
    \n
  1. For a start we can find all substrings of the given string and then check if the given string contains aman<\/B> or not.<\/li>\n
  2. We can find the total number of substrings in O(N2<\/sup>)<\/b> time and for each string finding aman<\/B> takes O(N)<\/b> time in the worst case. So, the total time complexity of this approach is O(N3<\/sup>)<\/b>.<\/li>\n
  3. Discussed approach is very lengthy and inefficient. So we have to find a new efficient approach to solve this problem.<\/li>\n<\/ol>\n
    Efficient Approach:<\/h4>\n
      \n
    1. \n
      For a given substring of given string S<\/b>, we can calculate the total number of pairs in it by, subtracting the sum of 3<\/b> and index of the first appearance of aman<\/b> from the length of the substring.<\/p>\n
          Total Number of pairs = len(sub) - (3 + ind)\n    and len(sub) = len(S) - start\n\n    where,\n\n    len(sub) = length of substring\n    len(S) = length of String\n    ind = index at which \"aman\" appeared for the first time in Substring 'sub'<\/code><\/pre>\n<\/li>\n
    2. \n
      We calculate this for all substrings from index 0 to last index and add that to our final count.<\/p>\n<\/li>\n
    3. \n
      We print the final count<\/b><\/p>\n<\/li>\n<\/ol>\n
      Example<\/h4>\n
        \n
      • \n
        Lets take string given in test case i.e. amanaaamanc<\/b>.
        \nWe check all substrings of given string ending at last index of given string, and size of substring must be greater than or equal to 4<\/b> i.e, size of aman<\/b><\/p>\n
        Such substrings are,
        \n"amanaaamanc"<\/code>
        \n"manaaamanc"<\/code>
        \n"anaaamanc"<\/code>
        \n"naaamanc"<\/code>
        \n"aaamanc"<\/code>
        \n"aamanc"<\/code>
        \n"amanc"<\/code>
        \n"manc"<\/code>
        \nSo we check, total number of substrings containing aman<\/b> atleast once.<\/p>\n<\/li>\n
      • \n
        For all substrings above:<\/p>\n<\/li>\n<\/ul>\n
        amanaaamanc<\/u>:<\/strong><\/p>\n
          \n
        • We observe fist appearance of aman<\/b> at index 0, so total number of pairs will be
          \nLength-(index+3)<\/code>
          \n11-(0+3)<\/code>
          \n11-3<\/code>
          \n8<\/code>  <\/li>\n
        • So, there will be total 8<\/b> pairs containing aman<\/b> atleast once. These pairs are (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9), (0,10), and (0,11)<\/code>.      <\/li>\n<\/ul>\n
          manaaamanc<\/u>:<\/strong><\/p>\n
            \n
          • \n
            We observe fist appearance of aman<\/b> at index 5, so total number of pairs will be
            \nLength-(index+3)<\/code>
            \n10-(5+3)<\/code>
            \n10-8<\/code>
            \n2<\/code>  <\/p>\n<\/li>\n
          • \n
            So, there will be total 2<\/b> pairs containing aman<\/b> atleast once. These pairs are (5,8) and (5,9)<\/code>.<\/p>\n<\/li>\n<\/ul>\n
            anaaamanc<\/u>:<\/strong><\/p>\n
              \n
            • \n
              We observe fist appearance of aman<\/b> at index 4, so total number of pairs will be
              \nLength-(index+3)<\/code>
              \n9-(4+3)<\/code>
              \n9-7<\/code>
              \n2<\/code>  <\/p>\n<\/li>\n
            • \n
              So, there will be total 2<\/b> pairs containing aman<\/b> atleast once. These pairs are (4,7) and (4,8)<\/code>.<\/p>\n<\/li>\n<\/ul>\n
              naaamanc<\/u>:<\/strong><\/p>\n
                \n
              • \n
                We observe fist appearance of aman<\/b> at index 3, so total number of pairs will be
                \nLength-(index+3)<\/code>
                \n8-(3+3)<\/code>
                \n8-6<\/code>
                \n2<\/code>  <\/p>\n<\/li>\n
              • \n
                So, there will be total 2<\/b> pairs containing aman<\/b> atleast once. These pairs are (3,6) and (3,7)<\/code>.    <\/p>\n<\/li>\n<\/ul>\n
                aaamanc<\/u>:<\/strong><\/p>\n
                  \n
                • \n
                  We observe fist appearance of "aman"<\/code> at index 2, so total number of pairs will be
                  \nLength-(index+3)<\/code>
                  \n7-(2+3)<\/code>
                  \n7-5<\/code>
                  \n2<\/code>  <\/p>\n<\/li>\n
                • \n
                  So, there will be total 2<\/b> pairs containing aman<\/b> atleast once. These pairs are (2,5) and (2,6)<\/code>.<\/p>\n<\/li>\n<\/ul>\n
                  aamanc<\/u>:<\/strong><\/p>\n
                    \n
                  • \n
                    We observe fist appearance of aman<\/b> at index 1, so total number of pairs will be
                    \nLength-(index+3)<\/code>
                    \n6-(1+3)<\/code>
                    \n6-4<\/code>
                    \n2<\/code>  <\/p>\n<\/li>\n
                  • \n
                    So, there will be total <\/b> pairs containing aman<\/b> atleast once. These pairs are (1,4) and (1,5)<\/code>.<\/p>\n<\/li>\n<\/ul>\n
                    amanc<\/u>:<\/strong><\/p>\n
                      \n
                    • \n
                      We observe fist appearance of aman<\/b> at index 0, so total number of pairs will be
                      \nLength-(index+3)<\/code>
                      \n5-(0+3)<\/code>
                      \n5-3<\/code>
                      \n2<\/code>  <\/p>\n<\/li>\n
                    • \n
                      So, there will be total <\/b> pairs containing aman<\/b> atleast once. These pairs are (0,3) and (0,4)<\/code>.<\/p>\n<\/li>\n<\/ul>\n
                      manc<\/u>:<\/strong><\/p>\n
                        \n
                      • We don’t find aman<\/b> in given string.  <\/li>\n
                      • So, there will be total 0<\/b> pairs containing aman<\/b> atleast once.<\/li>\n
                      • On counting total pairs from above-given procedure, we find total of 20<\/b> pairs.<\/li>\n<\/ul>\n
                        Solutions<\/h3>\n\t\t\t\t\t\t