This Problem was asked in a recent SDE intern round from Uber. There were 3 questions, I was only able to solve one of them. The second problem on the test was :

Problem 1 : A string A is called 'special' if it can be written like A = B + B. Empty string is also special.
Given a string S, you can perform :
i. Insert a new character anywhere inn the string.
ii. Remove a character.
iii. Replace character.
For a string, find the smallest possible number of steps to make given string S, a special string.
"xxxx","xyxy" and "abaaba" are examples of special strings.
"xxyy" and "xyx" are not special strings.

My Idea was to iterate at every position, and divide the string into two parts then find the minimum number of steps to make the two strings equal(Like Edit String Problem). It Got TLE in some test cases as the time complexity was O(n^3).

Example 1 :
Input : S1 = "aaxa"
Output : 1

Example 2 :
Input S1 = "cathatratmat"
Output : 2

Edit :
Example 3 :
Input S1 : "aabcdeccdecc"
Output : 4

Constraint :
1 <= S.length <= 5000

    int Edit_Distance(string W1, string W2) {//Edit : This is Levenshtein algorithm
        int n = W1.size() , m = W2.size() ;
        vector<vector<int> > V(n+1,vector<int>(m+1,0));//m+1 coloumns n+1 rows
 
        for(int i= n ; i >= 0; --i ) V[i][m] = n-i; 
        for(int i= m ; i >= 0; --i ) V[n][i] = m-i;
        
        for(int i = n-1 ; i >= 0 ; --i){
            for(int j = m-1; j>=0 ; --j){
                if(W1[i] == W2[j]) V[i][j] = V[i+1][j+1];
                else V[i][j] = min(V[i+1][j+1],min(V[i+1][j],V[i][j+1])) + 1;
            }            
        }    
        
        return V[0][0];
    }
	
	int Make_Special(string S1){
	int cost = INT_MAX;
	
	string S2(S1),S3;
	for(int i = 0,n=S1.size() ; i < n; i++)
	cost  = min(cost,Edit_Distance(S2  ,S3  ) ) , 
	S3 += S2[n-1-i] , S2.pop_back()  ;
	
	return cost;
	}

This is an O(n^3) solution and didn't get accepted, What can be a better approach to this problem?