Concepts Used

Strings

Difficulty Level

Easy

Problem Statement (Simplified):

Find the total number of pairs of indexes (i, j) such as subString(i, j) contains "aman" atleast once.

See original problem statement here

Test Case

Input:
1
amanaaamanc

Output:
20

Explanation:
Substrings 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.

Solving Approach :

Bruteforce Approach:

1) For a start we can find all substrings of the given string and then check if the given string contains "aman" or not.
2) We can find the total number of substrings in O(N^{2}) time and for each string finding aman takes O(N) time in the worst case. So, the total time complexity of this approach is O(N^{3}).
3) Discussed approach is very lengthy and inefficient. So we have go through some best online classes for coding to find a new efficient approach to solve this problem.

Efficient Approach:

1) For a given substring of given string S, we can calculate the total number of pairs in it by, subtracting the sum of 3 and index of the first appearance of aman from the length of the substring.

Total Number of pairs = len(sub) - (3 + ind)
and len(sub) = len(S) - start

where,

len(sub) = length of substring
len(S) = length of String
ind = index at which "aman" appeared for the first time in Substring 'sub'

2) We calculate this for all substrings from index 0 to last index and add that to our final count.
3) We print the final count.

Example

  • Lets take string given in test case i.e. "amanaaamanc".
  • We 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 i.e, size of "aman".
  • Such substrings are, "amanaaamanc","manaaamanc","anaaamanc","naaamanc","aaamanc","aamanc","amanc","manc". So we check, total number of substrings containing "aman"` atleast once.
  • For all substrings above:
    "amanaaamanc":
    > * We observe fist appearance of "aman" at index 0, so total number of pairs will be
    > => Length-(index+3)
    > => 11-(0+3)
    > => 11-3
    > => 8
    > So, there will be total 8 pairs containing "aman" atleast once. These pairs ar (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9), (0,10), and (0,11).

"manaaamanc":
> * We observe fist appearance of "aman" at index 5, so total number of pairs will be
> => Length-(index+3)
> => 10-(5+3)
> => 10-8
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (5,8) and (5,9).

"anaaamanc":
> * We observe fist appearance of "aman" at index 4, so total number of pairs will be
> => Length-(index+3)
> => 9-(4+3)
> => 9-7
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (4,7) and (4,8).

"naaamanc":
> * We observe fist appearance of "aman" at index 3, so total number of pairs will be
> => Length-(index+3)
> => 8-(3+3)
> => 8-6
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (3,6) and (3,7).

"aaamanc":
> * We observe fist appearance of "aman" at index 2, so total number of pairs will be
> => Length-(index+3)
> => 7-(2+3)
> => 7-5
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (2,5) and (2,6).

"aamanc":
> * We observe fist appearance of "aman" at index 1, so total number of pairs will be
> => Length-(index+3)
> => 6-(1+3)
> => 6-4
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (1,4) and (1,5).

"amanc":
> * We observe fist appearance of "aman" at index 0, so total number of pairs will be
> => Length-(index+3)
> => 5-(0+3)
> => 5-3
> => 2
> So, there will be total 2 pairs containing "aman" atleast once. These pairs ar (0,3) and (0,4).

"manc":
> * We don't find "aman" in given string.
> So, there will be total 0 pairs containing "aman" atleast once.

On counting total pairs from above-given procedure, we find total of 20 pairs.

Solutions

#include<stdio.h>

int main(){

  int test;
  scanf("%d",&test);

  while(test--){

    char a[100000];
    scanf("%s",a);

    int count = 0;

      for(int i=0; i<strlen(a); i++){
        int index = -1;
        for(int j=i; j+3<strlen(a); j++){
          if(a[j]=='a' && a[j+1]=='m' && a[j+2]=='a' && a[j+3] == 'n'){
            index = j-i;
            break;
          }
        }

        if(index != -1)
          count += strlen(a) - ( i + 3 + index  );

      }

    printf("%d\n",count);
  }

}

#include<bits/stdc++.h>
using namespace std;

int main(){

  int test;
  cin>>test;

  while(test--){

    char a[100000];
    cin>>a;

    int count = 0;

      for(int i=0; i<strlen(a); i++){
        int index = -1;
        for(int j=i; j+3<strlen(a); j++){
          if(a[j]=='a' && a[j+1]=='m' && a[j+2]=='a' && a[j+3] == 'n'){
            index = j-i;
            break;
          }
        }

        if(index != -1)
          count += strlen(a) - ( i + 3 + index  );

      }

    cout<<count<<endl;
  }

}

import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
public static void main(String args[]) throws IOException {

    Scanner sc= new Scanner(System.in);
    int test = sc.nextInt();
    while(test != 0){

        String a = sc.next();

        int count = 0;

        for(int i=0; i<a.length(); i++){
          int index = -1;
          for(int j=i; j+3<a.length(); j++){
            if(a.charAt(j)=='a' && a.charAt(j+1)=='m' && a.charAt(j+2)=='a' && a.charAt(j+3) == 'n'){
              index = j-i;
              break;
            }
          }

          if(index != -1)
            count += a.length() - ( i + 3 + index  );

        }

        System.out.println(count);
        test--;
    }
  }
}

Space Complexity of this approach would be O(1).

Previous post Square Moves
Next post Aman and Math

Leave a Reply

Your email address will not be published. Required fields are marked *