Last Updated: 24 Dec, 2021

Remove Duplicate Substrings

Moderate

Asked in companies

Solve now

Problem statement

Ninja has an ‘N’ character long string. He observed that the string consists of the same adjacent letters. So, he thought to remove some characters from the string using this operation.

In one operation, we can delete a substring having ‘K’ same adjacent characters. causing the left and the right side of the deleted substring to concatenate together.

Ninja applied this operation as many times as possible.

Your task is to find the resultant string after all operations.

You are given a string ‘S’ having ‘N’ lowercase letters and an integer ‘K’. Find the resultant string after all the operations are done.

For Example

If the given string S = “abcbaacd” and k = 2. In the first operation, we will remove ‘aa’ from the string. After that, we will concatenate the left and right strings as the resultant string will be “abcb” + “cd” = “abcbcd”.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of characters present in string S and ‘K’.

The following line contains the string ‘S’.

Output Format:

For each test case, print ‘an integer corresponding to the minimum number of swaps required.

Print the output of each test case 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 <= 10
1 <= N <= 10^4.
1 <= K <= 1000.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will simply check the string and if we found any substring having ‘K’ adjacent equal characters, we will remove that substring and make a recursive call for the new resultant string.

Algorithm:

Declare an integer ‘C’ to count the frequency of adjacent characters.
Set ‘C’ as 1.
For i in range 1 to the N -1:
- If S[i] == S[i-1] :
  - Set C as C+1.
- Else:
  - Set C as 1.
- If C == ‘K’:
  - Set ‘RES’ as “”.
  - If i-K >=0:
    - Set ‘RES’ as RES+substring of S from index 0 to (i-K).
  - If i+1<=(N-1):
    - Set ‘RES’ as RES + substring of S from index i+1 to (N-1).
  - Call the same function for the resultant string ‘RES’.
  - Call removeDuplicateSubstrings(N-K,RES).
Return ’S’.

Solve now

02 Approach

In this approach, we will first define an array of ‘C’ for size ‘N’.C[i] will store the number of the same adjacent characters till S[i]. Now, we will declare two pointers i and j.j will denote the ending index of our final resultant string and we will iterate i to check the frequency and calculate the value of C[i].wIf we found C[i] == ‘K’, we will delete that substring and update our j pointer.

At last the final resultant string will be the substring of S from index 0 to j-1.

Algorithm:

Declare an array ‘C’ of size ‘N’.
Set all values of C to 1.
Set ‘j’ as 1.
For i in range 1 to N-1:
- Set S[j] as S[i].
- If j > 0 and S[j] == S[j+1] :
  - C[j] = C[j]+1.
- Else:
  - C[j] = 1.
- If C[j] == ‘K’:
  - Delete the last K elements.
  - Set j as j-’K’.
- Increment j to j +1.
Return substring of S from index 0 to j-1.

Solve now

03 Approach

In this approach, we will build up a stack that will store two things character and frequency of that adjacent repetition of that character. We will simply iterate over the string and count the frequency of that adjacent repetition. Whenever we found a frequency of ‘K’ , we will pop that element from the stack and discard that substring from our final answer.

At last, we will form our resultant string using the elements of the stack.

Algorithm:

Declare a stack ‘ST’.
Push {S[0],1} into the stack ST.
For i in range 1 to N-1:
- If S[i] == character at top of ST.
  - Increment the Frequency of the top element of ST.
- Else:
  - Pust {S[i],1} into the stack ST.
- If the frequency of top element of stack == ‘K’:
  - Pop the top element from the stack ST.
Set ‘ANS’ as an empty string.
While the size of ST is greater than 0:
- Set F as the frequency of the top element.
- Set CH as the character of the top element.
- For i in range 0 to F:
  - Update ANS as ‘ANS’ + CH.
- Pop the top element from the stack ST.
Reverse the ‘ANS’ string.
Return ‘ANS’.

Solve now