Remove Duplicate Substrings

Moderate
0/80
Average time to solve is 45m
11 upvotes
Asked in companies
OracleFacebookGoldman Sachs

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
10 2
abcbacaacd
8 3
ababbbbc
Sample Output 1:
abcbad
ababc
Explanation of sample input 1:
For the first test case,

In the first operation, we will remove ‘aa’ from the string. The resultant string will be “abcbaccd”.In the second operation, we will remove ‘cc’ from the string. The resultant string will be “abcbad”.Now, we can’t apply any operation on the string. Hence, the resultant string is “abcbad”.


For the second test case:

In the first operation, we will remove ‘bbb’ from the string. The resultant string will be “ababc”.Now, we can’t apply any operation on the string. Hence, the resultant string is “ababc”.
Sample Input 2:
2
8 3
aaaallli
8 2
jjjjwwnh
Sample Output 2:
ai
nh
Hint

Check for each substring and apply the operations.

Approaches (3)
Brute Force.

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’.
Time Complexity

O(N*N/K), where ‘N’ is the number of characters in string ‘S’ and ‘K’ is the given number.

 

In this approach, we are checking the whole string for each operation possible and at worst there can be at maximum N/K operations possible. Hence, the overall time complexity is O(N*N/K).

Space Complexity

O(N/K), where ‘N’ is the number of characters in string ‘S’ and ‘K’ is the given number.

 

In this approach, there are at most N/K operations possible, and at max N/K recursive calls are possible so O(N/K) stack memory will be used. Hence, the overall space complexity is O(N/K).

Code Solution
(100% EXP penalty)
Remove Duplicate Substrings
Full screen
Console