Make string S equal to T after replacing some prefix characters in S
Given two strings S and T of equal length consisting of lowercase characters. In one operation, it is allowed to erase the 0th character of the string S and move it to any place in the string S, the task is to find the minimum number of operations required to convert S equal to T.
Examples:
Input: S = abab, T = abba
Output: 2
Explanation: In 1st operation erase a and move to the end, S = baba, In 2nd operation erase b and move to 2nd position, S = abba. Hence in 2 operations, we can make string S equal to T.Input: S = arc, T = cra
Output: 2
Explanation: In 1st move erase a and operation to the end, S = rca, In 2nd operation erase r and move to 1st position, S = cra. Hence in 2 operations, we can make string S equal to T.
Approach: This can be solved with the following idea:
Using binary search, look for the mid index and find the same index in the T string. If characters at both positions are equal, update the ans and right values. Repeat this step until the right becomes smaller than the left value.
Below are the steps involved in the implementation of the code:
- First for the case where after sorting both strings, if they are not equal then it is not possible to make both strings equal, otherwise, it is always possible to make both strings equal in a maximum of N moves
- Now, we can do a binary search on the answer taking the range as left = 1, right = N, where N is the length of string S.
- Now for any mid = (left + right)/2, remove the first mid characters and check if the remaining suffix of length (N – mid) length exists as a subsequence in the string T.
- If it exists, update right = mid, else left = mid + 1.
Below is the implementation of the above approach:
C++
// C++ code of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of operation required. int solve(string s, string t) { int n = s.size(); string ss = s, tt = t; sort(ss.begin(), ss.end()), sort(tt.begin(), tt.end()); // Check for equality if (ss != tt) { return -1; } int ans = n; int left = 0, right = n - 1; reverse(t.begin(), t.end()); while (left < right) { // Check for mid position int mid = (left + right) / 2; int cur = n - 1; for ( auto ch : t) { if (cur == mid - 1) break ; // If mid is equal to // current character if (ch == s[cur]) { --cur; } } if (cur == mid - 1) { right = mid; ans = right; } else { left = mid + 1; } } return ans; } // Driver code int main() { string s = "abab" ; string t = "abba" ; // Function call cout << solve(s, t); return 0; } |
Java
// Java code of the above approach import java.util.*; public class Main { // Function to find the minimum number // of operation required. public static int solve(String s, String t) { int n = s.length(); String ss = s, tt = t; char [] sArray = ss.toCharArray(); char [] tArray = tt.toCharArray(); Arrays.sort(sArray); Arrays.sort(tArray); ss = new String(sArray); tt = new String(tArray); // Check for equality if (!ss.equals(tt)) { return - 1 ; } int ans = n; int left = 0 , right = n - 1 ; t = new StringBuilder(t).reverse().toString(); while (left < right) { // Check for mid position int mid = (left + right) / 2 ; int cur = n - 1 ; for ( char ch : t.toCharArray()) { if (cur == mid - 1 ) break ; // If mid is equal to // current character if (ch == s.charAt(cur)) { --cur; } } if (cur == mid - 1 ) { right = mid; ans = right; } else { left = mid + 1 ; } } return ans; } // Driver code public static void main(String[] args) { String s = "abab" ; String t = "abba" ; // Function call System.out.println(solve(s, t)); } } // This code is contributed by Prajwal Kandekar |
Python3
# Python code of the above approach # Function to find the minimum # number of operation required def solve(s, t): n = len (s) sArray = sorted (s) tArray = sorted (t) ss = ''.join(sArray) tt = ''.join(tArray) # Check for equality if ss ! = tt: return - 1 ans = n left = 0 right = n - 1 t = t[:: - 1 ] while left < right: # Check for mid position mid = (left + right) / / 2 cur = n - 1 for ch in t: if cur = = mid - 1 : break # If mid is equal to current character if ch = = s[cur]: cur - = 1 if cur = = mid - 1 : right = mid ans = right else : left = mid + 1 return ans s = "abab" t = "abba" # Function call print (solve(s, t)) # This code is contributed by sankar. |
C#
// c# code of the above approach using System; public class GFG { // Function to find the minimum number of operations required. public static int Solve( string s, string t) { int n = s.Length; string ss = s; string tt = t; char [] sArray = ss.ToCharArray(); char [] tArray = tt.ToCharArray(); Array.Sort(sArray); Array.Sort(tArray); ss = new string (sArray); tt = new string (tArray); // Check for equality if (ss != tt) { return -1; } int ans = n; int left = 0; int right = n - 1; t = new string (ReverseString(t.ToCharArray())); while (left < right) { // Check for mid position int mid = (left + right) / 2; int cur = n - 1; foreach ( char ch in t) { if (cur == mid - 1) break ; // If mid is equal to current character if (ch == s[cur]) { --cur; } } if (cur == mid - 1) { right = mid; ans = right; } else { left = mid + 1; } } return ans; } // Helper function to reverse a string public static char [] ReverseString( char [] s) { int left = 0; int right = s.Length - 1; while (left < right) { char temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } return s; } // Driver code public static void Main( string [] args) { string s = "abab" ; string t = "abba" ; // Function call Console.WriteLine(Solve(s, t)); } } |
Javascript
// Function to find the minimum number // of operation required. function solve(s, t) { let n = s.length; let ss = s, tt = t; ss = ss.split( '' ).sort().join( '' ); tt = tt.split( '' ).sort().join( '' ); // Check for equality if (ss !== tt) { return -1; } let ans = n; let left = 0, right = n - 1; t = t.split( '' ).reverse().join( '' ); while (left < right) { // Check for mid position let mid = Math.floor((left + right) / 2); let cur = n - 1; for (let ch of t) { if (cur === mid - 1) break ; // If mid is equal to // current character if (ch === s[cur]) { --cur; } } if (cur === mid - 1) { right = mid; ans = right; } else { left = mid + 1; } } // Return result return ans; } // Driver code let s = "abab" ; let t = "abba" ; console.log(solve(s, t)); |
2
Time Complexity: O(N)
Auxiliary Space: O(1)