  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Aman String

Last Updated on August 22, 2022 by Gokul Kannan Strings

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(N2) 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(N3).
3. Discussed approach is very lengthy and inefficient. So we have 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 are `(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 are `(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 are `(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 are `(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 are `(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 pairs containing aman atleast once. These pairs are `(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 pairs containing aman atleast once. These pairs are `(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;
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;
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--;
}
}
}
```
```for _ in range(int(input())):

a = input()
count = 0

for i in range(len(a)):

index = -1

for j in range(i, len(a) - 3):

if(a[j] == 'a' and a[j+1] == 'm' and a[j+2] == 'a' and a[j+3] == 'n'):

index = j-i
break

if(index != -1):
count += len(a) - ( i + 3 + index )

print(count)

```

[forminator_quiz id="744"]

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

This article tried to discuss the concept of Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.