Substrings differ by one

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Samsung

Problem statement

This time Ninja is fighting with string man, but string man is too powerful for the Ninja to defeat him alone. So Ninja needs your help to defeat him, Ninja has two strings ‘S’ and ‘T’ to defeat string man Ninja has to find the number of substrings in ‘S’ that differ from some substrings of ‘T’ by exactly one character.

Help Ninja by telling him the number of such types of substrings.

For example:

‘S’ = “aba” ‘T’ = “aca” then 
 (a, c)
 (b, a)
 (b, c)
 (b, a)
 (a, c)
 (ab, ac)
 (ba, ca)
 (aba, aca)
 Total 8 strings.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The next two lines of each test case contains two strings ‘S’ and ‘T’.
Output Format : 
For each test case, print a single line containing a single integer denoting the number of described substrings. 

The output for each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N, M <= 200

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ is the length of the strings ‘S’ and ‘T’ respectively.

Time limit: 1 sec.

Sample Input 1:

2
ab
ac
aa
bb

Sample Output 1:

4
4

Explanation of Sample Output 1:

Test Case 1 : Four cases are described below:
( a, c )
( b, a )
( b, c )
( ab, ac )

Test Case 2:  Four cases are described below:
( a , b )
( a , b )
( a , b )
( a , b )

Sample Input 2:

2
codingninjasisawesome
codingninjasisawesome
aabbcddee
aabbeddee

Sample Output 2:

444
106
Hint

Try to calculate number of substring using two pointers.

Approaches (2)
Brute force

Here, the idea is to compare all substrings and add only those substrings resulting in only one mismatched character. 

We can achieve this by storing the number of mismatched characters in each substring.

 

Algorithm:

  • Declare a variable ‘RES’ = 0
  • for(i : 0 -> S.length )
  • for(j : 0 -> T.length )
    • Declare 2 variables ‘MISS’  = 0, ‘P’ = 0
    • while( i + P < S.length and j + P < T.length )
      • P = P + 1
      • if( S[i + P] ! = T[ j + P] ) MISS++;
      • if(MISS > 1) break
      • RES += MISS
  • Return RES.
Time Complexity

O( N * M * min(N, M) ), where ‘N’ and ‘M’ is the length of the given strings ‘S’ and ‘T’.

 

We are running three nested loops till strings length.

Space Complexity

O( 1 ).

 

We are storing nothing so space complexity is O(1). 

Code Solution
(100% EXP penalty)
Substrings differ by one
Full screen
Console