Construct The String

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in companies
BNY MellonMicrosoftUber

Problem statement

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”.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input-1
2
3
aba
4
aaaa
Sample Output-1
3
3
Explanation for Sample Input 1:
For test case 1:
    Add ‘a’ to the string. Hence the current string is ‘a’.
    Add ‘b’ to the string. Hence the current string is “ab”.
    Add ‘a’ to the string. Hence the current string is “aba”.
    We needed three operations to get the desired string.
For test case 2:
    Add ‘a’ to the string. Hence the current string is ‘a’.
    Add ‘a’ to the string. Hence the current string is “aa”.
    Add “aa” to the string. Hence the current string is “aaaa”.
    We needed three operations to get the desired string.
Sample Input -2
2
6
abcabc
2
aa
Sample Output -2
4
2
Hint

When should you use the second operation?

Approaches (2)
Brute Force

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

O(N * N), Where 'N' is the length of the string.

Comparison of two strings has O(|S|) time complexity. Hence the overall complexity is O(N * N).

Space Complexity

O(N), Where 'N' is the length of the string.

We are creating an array of length ‘N’. Hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Construct The String
Full screen
Console