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(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[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.

Leave a Reply

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