Last Updated: 25 Nov, 2021
Construct The String
Moderate
Asked in companies
Your friend gave you a challenge. He gave you a string ‘S’ of length ‘N’ consisting only of lowercase English alphabets. He asked you to construct the given string using the minimum number of operations. In each operation, you can do one of the steps.
1) Add a lowercase English alphabet at the end of the string.
2) Create a copy of the string and concatenate both of the strings.
Initially, you have an empty string. So if you perform the second operation, you will get an empty string.
For example: If the current string is “abc”, then after performing the second operation, the current string will be “abcabc”.
Input Format-
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains an integer, ‘N’, denoting the length of the input string S.
The following line contains the string ‘S’ of length ‘N’.
Output Format-
For each test case, you have to print an integer denoting the minimum number of operations required to form the given string ‘S’.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints -
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
Note- Sum of ‘N’ over all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: We should use the second operation only if the S[0...i] = S[(i + 1).…..(2 * i + 1)], where S[i…..j] denotes the string from index ‘i’ to ‘j’. We can always use the first operation.
We will store the minimum operations required to construct the first ‘i’ characters.
Algorithm:
- Create an array ‘dp’ of length ‘N’ and initialize all its values to INT_MAX.
- Update dp[0] to 1.
- Iterate using a for loop from i = ‘1’ to ‘N - 1’.
- Update dp[i] to min(dp[i], dp[i - 1] + 1).
- If S[0...i] == S[(i + 1).…..(2 * i + 1)].
- Update dp[2 * i + 1] to dp[i] + 1.
- Print ‘dp[N - 1]’.
Prerequisite: Z - Algorithm
Approach: In the second operation, we are just adding the length |s| prefix of the string ‘S’ to the current string ‘s’. So we can use the Z-Algorithm to store for each index the length of the longest substring starting from S[i], which is also a prefix of the string ‘S’. If Z[i] >= ‘i’, we can use the second operation.
Algorithm:
- Func z_function().
- Create two variables, ‘L’, ‘R’ and initialize both of them to 0.
- Create an array ‘Z’ of length ‘N’.
- Iterate using a for loop from i = ‘1’ to ‘N - 1’.
- If ‘i’ <= ‘R’.
- Update Z[i] to min (R - i + 1, Z[i - L]).
- while (i + Z[i] < N) and (S[Z[i]] == S[i + Z[i]]).
- Increment Z[i] by 1.
- If i + Z[i] - 1 > R.
- Update L to i.
- Update R to i + Z[i] - 1.
- If ‘i’ <= ‘R’.
- Return Z.
- Func Main().
- Create an array ‘dp’ of length ‘N’ and initialize all its values to INT_MAX.
- Update dp[0] to 1.
- Use z_function() to get the ‘Z’ array.
- Iterate using a for loop from i = ‘1’ to ‘N - 1’.
- Update dp[i] to min(dp[i], dp[i - 1] + 1).
- If Z[i] >= i.
- Update dp[2 * i - 1] to dp[i - 1] + 1.
- Print ‘dp[N - 1]’.
Similar problems