Type it!

Problem Statement - link #

Geek is extremely punctual but today even he is not feeling like doing his homework assignment. He must start doing it immediately in order to meet the deadline. For the assignment, Geek needs to type a string s. To reduce his workload, he has decided to perform one of the following two operations till he gets the string.

• Append a character at the end of the string.
• Append the string formed thus far to the end of the string. (This can not be done more than once.)

Help Geek find the minimum operations required to type the given string.

Your Task:

You don’t need to read input or print anything. Your task is to complete the function minOperation() which takes a string s as input parameter and returns the minimum operations required to type it.

Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Input:
s = abcabca
Output: 5
Explanation: a -> ab -> abc -> abcabc 
-> abcabca

Example 2:

Input:
s = abcdefgh
Output: 8
Explanation: a -> ab -> abc -> abcd 
-> abcde -> abcdef -> abcdefg -> abcdefgh

Constraints #

• 1 <= N <= 1000

Solutions #

class Solution {
  public:
    int minOperation(string s) {
        // code here
        int count=1, valid=1;
        string temp;
        temp.push_back(s[0]);
        int i=1;
        while( i < s.length() ) {
            int tn=temp.length();
            
            if( i+tn <= s.length() && s.substr(i,tn) == temp ) {
                temp += temp;
                i += tn;
                count += tn;
                valid = max(valid, tn);
            }
            else {
                temp.push_back(s[i]);
                i++;
                count++;
            }
            
        }
        return count-valid+1;
    }
};