Last Updated on August 22, 2022 by Gokul Kannan
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:
- For a start we can find all substrings of the given string and then check if the given string contains aman or not.
- 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).
- Discussed approach is very lengthy and inefficient. So we have to find a new efficient approach to solve this problem.
Efficient Approach:
-
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' -
We calculate this for all substrings from index 0 to last index and add that to our final count.
-
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 amanSuch 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[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--;
}
}
}
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.