Last Updated: 2 Apr, 2021

Substrings differ by one

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The idea here is to optimize the previous approach using dynamic programming. As we are calculating the l and r value for every mismatched character again and again so we will precompute sizes of a matching substring ending at position ( i, j ) and starting at position

( i, j )

DPL[ i ][ j ] : size of matching substring ending at position (i, j)

DPR[ i ][ j ] : size of matching substring starting at position (i, j)

Algorithm:

Declare two 2-d array DPL and DPR of size (N + 1) x (M + 1) initialise both with all ‘0’ and variable ANS = 0
Run nested loop
- for( i : 1 -> N )
- for( j : 1 -> M )
  - if(S[ i - 1] = T[ j - 1 ])
  - DPL[ i ][ j ] = 1 + DPL[i - 1][j - 1]
Again implemented steps for DPR but in reverse i.e. from N -> 1 and M -> 1
After this, for each mismatched character in ‘s’ and ‘t’
- ans += DPL[i][j] * DPR[i + 1][j + 1]
Return ANS.

Solve now