Given two strings A and B of length N and M respectively and an array arr[] consisting of K integers, the task is to check if the string B can be obtained from the string A by swapping any pair of adjacent characters of the string A any number of times such that the swapped indices are not present in the array arr[]. If it is possible to convert string A to string B, print “Yes”. Otherwise, print “No”.
Examples:
Input: A = “abcabka”, B = “acbakba”, arr[] = {0, 3, 6}
Output: Yes
Explanation:
Swap A1 and A2. Now the string becomes A = “acbabka”.
Swap A4 and A5. Now the string becomes A = “acbakba”, which is the same as string B.Input: A = “aaa”, B = “bbb”, arr[] = {0}
Output : No
Approach: Follow the below steps to solve the problem:
- If the length of both the strings are not equal, then string A can’t be transformed to string B. Therefore, print “No”.
- Traverse the given array arr[] and check if characters at A[arr[i]] and B[arr[i]] are same or not. If found to be true, then print “No”. Otherwise, perform the following steps:
- If the first element of arr[i] is not 0:
- Store all characters of A and B from 0 to arr[i] in two strings, say X and Y.
- Find the frequency of characters of string X and Y.
- If the frequency of all characters is the same, print “No“.
- Similarly, if the last element of arr[i] is not equal to the element at index (N – 1), then:
- Store all characters of A and B from (arr[i] + 1) to N in two strings, say X and Y.
- Find the frequency of characters of string X and Y.
- If the frequency of all characters is the same, print “No“.
- Iterate a loop from 1 to N and initialize two pointers, L = arr[i – 1] and R = arr[i]:
- Store all characters of A and B from (L + 1) to R in two strings, say X and Y.
- Find the frequency of characters of string X and Y.
- If the frequency of all characters is the same, print “Yes”. Otherwise, print “No”.
- If the first element of arr[i] is not 0:
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count frequency of the // characters of two given strings bool isEqual(string& A, string& B) { // Stores the frequencies of // characters of strings A and B map< char , int > mp, mp1; // Traverse the string A for ( auto it : A) { // Update frequency of // each character mp[it]++; } // Traverse the string B for ( auto it : B) { // Update frequency of // each character mp1[it]++; } // Traverse the Map for ( auto it : mp) { // If the frequency a character // is not the same in both the strings if (it.second != mp1[it.first]) { return false ; } } return true ; } // Function to check if it is possible // to convert string A to string B void IsPossible(string& A, string& B, int arr[], int N) { // Base Case if (A == B) { cout << "Yes" << endl; return ; } // If length of both the // strings are not equal if (A.length() != B.length()) { cout << "No" << endl; return ; } // Traverse the array and check // if the blocked indices // contains the same character for ( int i = 0; i < N; i++) { int idx = arr[i]; // If there is a different // character, return No if (A[idx] != B[idx]) { cout << "No" << endl; return ; } } // If the first index is not present if (arr[0]) { string X = "" ; string Y = "" ; // Extract characters from // string A and B for ( int i = 0; i < arr[0]; i++) { X += A[i]; Y += B[i]; } // If frequency is not same if (!isEqual(A, B)) { cout << "No" << endl; return ; } } // If last index is not present if (arr[N - 1] != (A.length() - 1)) { string X = "" ; string Y = "" ; // Extract characters from // string A and B for ( int i = arr[N - 1] + 1; i < A.length(); i++) { X += A[i]; Y += B[i]; } // If frequency is not same if (!isEqual(A, B)) { cout << "No" << endl; return ; } } // Traverse the array arr[] for ( int i = 1; i < N; i++) { int L = arr[i - 1]; int R = arr[i]; string X = "" ; string Y = "" ; // Extract characters from strings A and B for ( int j = L + 1; j < R; j++) { X += A[j]; Y += B[j]; } // If frequency is not same if (!isEqual(A, B)) { cout << "No" << endl; return ; } } // If all conditions are satisfied cout << "Yes" << endl; } // Driver Code int main() { string A = "abcabka" ; string B = "acbakba" ; int arr[] = { 0, 3, 6 }; int N = sizeof (arr) / sizeof (arr[0]); IsPossible(A, B, arr, N); return 0; } |
Java
// Java program for the above approach // importing input-output and utility classes import java.io.*; import java.util.*; class GFG { // method to count frequency of the // characters of two given strings static boolean isEqual(String A, String B) { // storing the frequencies of characters HashMap<Character, Integer> map = new HashMap<>(); HashMap<Character, Integer> map2 = new HashMap<>(); // Traversing the String A for ( int i = 0 ; i < A.length(); i++) { if (map.containsKey(A.charAt(i))) map.put(A.charAt(i), map.get(A.charAt(i)) + 1 ); else map.put(A.charAt(i), 1 ); } // Traversing the String B for ( int i = 0 ; i < B.length(); i++) { if (map.containsKey(B.charAt(i))) map.put(B.charAt(i), map.get(B.charAt(i)) + 1 ); else map.put(B.charAt(i), 1 ); } // checking if both map have same character // frequency if (!map.equals(map2)) return false ; return true ; } // method to check possibility to convert A into B static void isPossible(String A, String B, int arr[], int N) { // Base Case if (A.equals(B)) { System.out.println( "Yes" ); return ; } // If length is not equal if (A.length() != B.length()) { System.out.println( "No" ); return ; } for ( int i = 0 ; i < N; i++) { int idx = arr[i]; if (A.charAt(idx) != B.charAt(idx)) { System.out.println( "No" ); return ; } } // If first index is not present if (arr[ 0 ] == 0 ) { String X = "" ; String Y = "" ; // Extracting Characters from A and B for ( int i = 0 ; i < arr[ 0 ]; i++) { X += A.charAt(i); Y += B.charAt(i); } // If frequency is not same if (!isEqual(A, B)) { System.out.println( "No" ); return ; } } // If last index is not present if (arr[N - 1 ] != (A.length() - 1 )) { String X = "" ; String Y = "" ; for ( int i = arr[N - 1 ] + 1 ; i < A.length(); i++) { X += A.charAt(i); Y += B.charAt(i); } if (!isEqual(A, B)) { System.out.println( "No" ); return ; } } // Traversing the Array for ( int i = 1 ; i < N; i++) { int L = arr[i - 1 ]; int R = arr[i - 1 ]; String X = "" ; String Y = "" ; // Extract Characters from Strings A and B for ( int j = L + 1 ; j < R; j++) { X += A.charAt(j); Y += B.charAt(j); } // if frequency is not same if (!isEqual(A, B)) { System.out.println( "No" ); return ; } } // if all condition satisfied System.out.println( "Yes" ); } // main method public static void main(String[] args) { String A = "abcabka" ; String B = "abcabka" ; int arr[] = { 0 , 3 , 6 }; int N = arr.length; // calling method isPossible(A, B, arr, N); } } |
Python3
# Python3 program for the above approach from collections import defaultdict # Function to count frequency of the # characters of two given strings def isEqual(A, B): # Stores the frequencies of # characters of strings A and B mp = defaultdict( int ) mp1 = defaultdict( int ) # Traverse the string A for it in A: # Update frequency of # each character mp[it] + = 1 # Traverse the string B for it in B: # Update frequency of # each character mp1[it] + = 1 # Traverse the Map for it in mp: # If the frequency a character # is not the same in both the strings if (mp[it] ! = mp1[it]): return False return True # Function to check if it is possible # to convert string A to string B def IsPossible(A, B, arr, N): # Base Case if (A = = B): print ( "Yes" ) return # If length of both the # strings are not equal if ( len (A) ! = len (B)): print ( "No" ) return # Traverse the array and check # if the blocked indices # contains the same character for i in range (N): idx = arr[i] # If there is a different # character, return No if (A[idx] ! = B[idx]): print ( "No" ) return # If the first index is not present if (arr[ 0 ]): X = "" Y = "" # Extract characters from # string A and B for i in range (arr[ 0 ]): X + = A[i] Y + = B[i] # If frequency is not same if ( not isEqual(A, B)): print ( "No" ) return # If last index is not present if (arr[N - 1 ] ! = ( len (A) - 1 )): X = "" Y = "" # Extract characters from # string A and B for i in range (arr[N - 1 ] + 1 , len (A)): X + = A[i] Y + = B[i] # If frequency is not same if ( not isEqual(A, B)): print ( "No" ) return # Traverse the array arr[] for i in range ( 1 , N): L = arr[i - 1 ] R = arr[i] X = "" Y = "" # Extract characters from strings A and B for j in range (L + 1 , R): X + = A[j] Y + = B[j] # If frequency is not same if ( not isEqual(A, B)): print ( "No" ) return # If all conditions are satisfied print ( "Yes" ) # Driver Code if __name__ = = "__main__" : A = "abcabka" B = "acbakba" arr = [ 0 , 3 , 6 ] N = len (arr) IsPossible(A, B, arr, N) # This code is contributed by ukasp |
C#
// C# program for the above approach // importing input-output and utility classes using System; using System.Collections.Generic; class GFG { // method to count frequency of the // characters of two given strings static bool isEqual( string A, string B) { // storing the frequencies of characters Dictionary< char , int > map = new Dictionary< char , int >(); Dictionary< char , int > map2 = new Dictionary< char , int >(); // Traversing the String A for ( int i = 0; i < A.Length; i++) { if (map.ContainsKey(A[i])) map[A[i]] = map[A[i]] + 1; else map.Add(A[i], 1); } // Traversing the String B for ( int i = 0; i < B.Length; i++) { if (map2.ContainsKey(B[i])) map2[B[i]] = map2[B[i]] + 1; else map2.Add(B[i], 1); } // checking if both map have same character // frequency if (!map.Equals(map2)) return false ; return true ; } // method to check possibility to convert A into B static void isPossible( string A, string B, int [] arr, int N) { // Base Case if (A.Equals(B)) { Console.WriteLine( "Yes" ); return ; } // If length is not equal if (A.Length != B.Length) { Console.WriteLine( "No" ); return ; } for ( int i = 0; i < N; i++) { int idx = arr[i]; if (A[idx] != B[idx]) { Console.WriteLine( "No" ); return ; } } // If first index is not present if (arr[0] == 0) { String X = "" ; String Y = "" ; // Extracting Characters from A and B for ( int i = 0; i < arr[0]; i++) { X += A[i]; Y += B[i]; } // If frequency is not same if (!isEqual(A, B)) { Console.WriteLine( "No" ); return ; } } // If last index is not present if (arr[N - 1] != (A.Length - 1)) { string X = "" ; string Y = "" ; for ( int i = arr[N - 1] + 1; i < A.Length; i++) { X += A[i]; Y += B[i]; } if (!isEqual(A, B)) { Console.WriteLine( "No" ); return ; } } // Traversing the Array for ( int i = 1; i < N; i++) { int L = arr[i - 1]; int R = arr[i - 1]; string X = "" ; string Y = "" ; // Extract Characters from Strings A and B for ( int j = L + 1; j < R; j++) { X += A[j]; Y += B[j]; } // if frequency is not same if (!isEqual(A, B)) { Console.WriteLine( "No" ); return ; } } // if all condition satisfied Console.WriteLine( "Yes" ); } // main method public static void Main() { string A = "abcabka" ; string B = "abcabka" ; int [] arr = { 0, 3, 6 }; int N = arr.Length; // calling method isPossible(A, B, arr, N); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to count frequency of the // characters of two given strings function isEqual(A, B) { // Stores the frequencies of // characters of strings A and B let mp = new Map(); let mp1 = new Map(); // Traverse the string A for (let it of A) { // Update frequency of // each character if (mp.has(it)) { mp.set(it, mp.get(it) + 1) } else { mp.set(it, 1) } } // Traverse the string B for (let it of B) { // Update frequency of // each character if (mp1.has(it)) { mp1.set(it, mp1.get(it) + 1) } else { mp1.set(it, 1) } } // Traverse the Map for (let it of mp) { // If the frequency a character // is not the same in both the strings if (it[1] != mp1.get(it[0])) { return false ; } } return true ; } // Function to check if it is possible // to convert string A to string B function IsPossible(A, B, arr, N) { // Base Case if (A == B) { document.write( "Yes" + "<br>" ); return ; } // If length of both the // strings are not equal if (A.length != B.length) { document.write( "No" + "<br>" ); return ; } // Traverse the array and check // if the blocked indices // contains the same character for (let i = 0; i < N; i++) { let idx = arr[i]; // If there is a different // character, return No if (A[idx] != B[idx]) { document.write( "No" + "<br>" ); return ; } } // If the first index is not present if (arr[0]) { let X = "" ; let Y = "" ; // Extract characters from // string A and B for (let i = 0; i < arr[0]; i++) { X += A[i]; Y += B[i]; } // If frequency is not same if (!isEqual(A, B)) { document.write( "No" + "<br>" ); return ; } } // If last index is not present if (arr[N - 1] != (A.length - 1)) { let X = "" ; let Y = "" ; // Extract characters from // string A and B for (let i = arr[N - 1] + 1; i < A.length; i++) { X += A[i]; Y += B[i]; } // If frequency is not same if (!isEqual(A, B)) { document.write( "No" + "<br>" ); return ; } } // Traverse the array arr[] for (let i = 1; i < N; i++) { let L = arr[i - 1]; let R = arr[i]; let X = "" ; let Y = "" ; // Extract characters from strings A and B for (let j = L + 1; j < R; j++) { X += A[j]; Y += B[j]; } // If frequency is not same if (!isEqual(A, B)) { document.write( "No" + "<br>" ); return ; } } // If all conditions are satisfied document.write( "Yes" + "<br>" ); } // Driver Code let A = "abcabka" ; let B = "acbakba" ; let arr = [ 0, 3, 6 ]; let N = arr.length IsPossible(A, B, arr, N); // This code is contributed by gfgking </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach:
- Check if the length of strings A and B are equal, if not, return false.
- Create a 2D boolean dp table of size N x M, where N and M are the length of strings A and B respectively.
- Initialize dp[0][0] as true if A[0] == B[0].
- Initialize dp[0][j] for j > 0, using the constraints given in the arr vector.
- Initialize dp[i][0] for i > 0, using the constraints given in the arr vector.
- Fill the remaining cells of the dp table using the given constraints, and the following conditions:
If A[i] == B[j], then dp[i][j] = dp[i-1][j-1]
If i > 1 and j > 0 and A[i] == B[j-1] and A[i-1] == B[j] and the constraints allow, then dp[i][j] = dp[i-2][j-2]
If j > 1 and A[i] == B[j-2] and A[i] == B[j-1] and the constraints allow, then dp[i][j] = dp[i][j-2]
If i > 1 and A[i] == B[j] and A[i-1] == B[j-1] and the constraints allow, then dp[i][j] = dp[i-2][j-1] - Return the value of dp[N-1][M-1].
- In the main function, call the isPossible function with the given input strings A and B, and the array arr.
- If isPossible returns true, print “Yes”, else print “No”.
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> #include <cstring> using namespace std; bool isPossible(string A, string B, vector< int > arr) { int N = A.length(); int M = B.length(); if (N != M) { return false ; } // Create a 2D boolean array to store if it is possible to // transform A[0...i] to B[0...j] with the given constraints bool dp[N][M]; memset (dp, false , sizeof (dp)); // Initialize dp[0][0] as true if A[0] == B[0] dp[0][0] = (A[0] == B[0]); // Initialize dp[0][j] for j > 0 for ( int j = 1; j < M; j++) { dp[0][j] = (A[0] == B[j]); dp[0][j] = dp[0][j] && (arr[0] != j); dp[0][j] = dp[0][j] && dp[0][j - 1]; } // Initialize dp[i][0] for i > 0 for ( int i = 1; i < N; i++) { dp[i][0] = (A[i] == B[0]); dp[i][0] = dp[i][0] && (arr[0] != i); dp[i][0] = dp[i][0] && dp[i - 1][0]; } // Fill the remaining cells of the dp table for ( int i = 1; i < N; i++) { for ( int j = 1; j < M; j++) { dp[i][j] = false ; if (A[i] == B[j]) { dp[i][j] = dp[i][j] || dp[i - 1][j - 1]; } if (i > 1 && j > 0 && A[i] == B[j - 1] && A[i - 1] == B[j] && arr[j - 1] != j && arr[j] != j - 1) { dp[i][j] = dp[i][j] || dp[i - 2][j - 2]; } if (j > 1) { dp[i][j] = dp[i][j] || (A[i] == B[j - 2] && A[i] == B[j - 1] && arr[j - 2] != j && arr[j - 1] != j && dp[i][j - 2]); } if (i > 1) { dp[i][j] = dp[i][j] || (A[i] == B[j] && A[i - 1] == B[j - 1] && arr[j] != j && arr[j - 1] != j - 1 && dp[i - 2][j - 1]); } } } return dp[N - 1][M - 1]; } int main() { string A = "abcabka" ; string B = "acbakba" ; vector< int > arr = {0, 3, 6}; if (isPossible(A, B, arr)) { cout << "Yes\n" ; } else { cout << "No\n" ; } } //This code is contributed by rudra1807raj |
Java
public class Main { static boolean isPossible(String A, String B, int [] arr) { int N = A.length(); int M = B.length(); // Create a 2D boolean array to store if it is possible to // transform A[0...i] to B[0...j] with the given constraints boolean [][] dp = new boolean [N][M]; // Initialize dp[0][0] as True if A[0] == B[0] dp[ 0 ][ 0 ] = A.charAt( 0 ) == B.charAt( 0 ); // Initialize dp[0][j] for j > 0 for ( int j = 1 ; j < M; j++) { dp[ 0 ][j] = A.charAt( 0 ) == B.charAt(j) && !contains(arr, j) && dp[ 0 ][j - 1 ]; } // Initialize dp[i][0] for i > 0 for ( int i = 1 ; i < N; i++) { dp[i][ 0 ] = A.charAt(i) == B.charAt( 0 ) && !contains(arr, i) && dp[i - 1 ][ 0 ]; } // Fill the remaining cells of the dp table for ( int i = 1 ; i < N; i++) { for ( int j = 1 ; j < M; j++) { dp[i][j] = false ; if (A.charAt(i) == B.charAt(j)) { dp[i][j] = dp[i][j] || dp[i - 1 ][j - 1 ]; } if (i > 1 && j > 0 && A.charAt(i) == B.charAt(j - 1 ) && A.charAt(i - 1 ) == B.charAt(j) && !contains(arr, j) && !contains(arr, j - 1 )) { dp[i][j] = dp[i][j] || dp[i - 2 ][j - 2 ]; } if (j > 1 ) { dp[i][j] = dp[i][j] || (A.charAt(i) == B.charAt(j - 2 ) && A.charAt(i) == B.charAt(j - 1 ) && !contains(arr, j - 2 ) && !contains(arr, j - 1 ) && dp[i][j - 2 ]); } if (i > 1 ) { dp[i][j] = dp[i][j] || (A.charAt(i) == B.charAt(j) && A.charAt(i - 1 ) == B.charAt(j - 1 ) && !contains(arr, j) && !contains(arr, j - 1 ) && dp[i - 2 ][j - 1 ]); } } } return dp[N - 1 ][M - 1 ]; } // Helper method to check if an array contains a given value static boolean contains( int [] arr, int value) { for ( int num : arr) { if (num == value) { return true ; } } return false ; } public static void main(String[] args) { String A = "abcabka" ; String B = "acbakba" ; int [] arr = { 0 , 3 , 6 }; if (isPossible(A, B, arr)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } |
Python3
def isPossible(A, B, arr): N = len (A) M = len (B) # Create a 2D boolean array to store if it is possible to # transform A[0...i] to B[0...j] with the given constraints dp = [[ False ] * M for _ in range (N)] # Initialize dp[0][0] as True if A[0] == B[0] dp[ 0 ][ 0 ] = A[ 0 ] = = B[ 0 ] # Initialize dp[0][j] for j > 0 for j in range ( 1 , M): dp[ 0 ][j] = A[ 0 ] = = B[j] and ( not j in arr) and dp[ 0 ][j - 1 ] # Initialize dp[i][0] for i > 0 for i in range ( 1 , N): dp[i][ 0 ] = A[i] = = B[ 0 ] and ( not i in arr) and dp[i - 1 ][ 0 ] # Fill the remaining cells of the dp table for i in range ( 1 , N): for j in range ( 1 , M): dp[i][j] = False if A[i] = = B[j]: dp[i][j] = dp[i][j] or dp[i - 1 ][j - 1 ] if i > 1 and j > 0 and A[i] = = B[j - 1 ] and A[i - 1 ] = = B[j] and ( not j in arr) and ( not (j - 1 ) in arr): dp[i][j] = dp[i][j] or dp[i - 2 ][j - 2 ] if j > 1 : dp[i][j] = dp[i][j] or (A[i] = = B[j - 2 ] and A[i] = = B[j - 1 ] and ( not (j - 2 ) in arr) and ( not (j - 1 ) in arr) and dp[i][j - 2 ]) if i > 1 : dp[i][j] = dp[i][j] or (A[i] = = B[j] and A[i - 1 ] = = B[j - 1 ] and ( not j in arr) and ( not (j - 1 ) in arr) and dp[i - 2 ][j - 1 ]) return dp[N - 1 ][M - 1 ] # Example usage A = "abcabka" B = "acbakba" arr = [ 0 , 3 , 6 ] if isPossible(A, B, arr): print ( "Yes" ) else : print ( "No" ) |
C#
using System; using System.Collections.Generic; class Program { static bool IsPossible( string A, string B, List< int > arr) { int N = A.Length; int M = B.Length; if (N != M) { return false ; } // Create a 2D boolean array to store if it is possible to // transform A[0...i] to B[0...j] with the given constraints bool [,] dp = new bool [N, M]; // Initialize dp[0][0] as true if A[0] == B[0] dp[0, 0] = (A[0] == B[0]); // Initialize dp[0][j] for j > 0 for ( int j = 1; j < M; j++) { dp[0, j] = (A[0] == B[j]); dp[0, j] = dp[0, j] && !arr.Contains(j); dp[0, j] = dp[0, j] && dp[0, j - 1]; } // Initialize dp[i][0] for i > 0 for ( int i = 1; i < N; i++) { dp[i, 0] = (A[i] == B[0]); dp[i, 0] = dp[i, 0] && !arr.Contains(i); dp[i, 0] = dp[i, 0] && dp[i - 1, 0]; } // Fill the remaining cells of the dp table for ( int i = 1; i < N; i++) { for ( int j = 1; j < M; j++) { dp[i, j] = false ; if (A[i] == B[j]) { dp[i, j] = dp[i, j] || dp[i - 1, j - 1]; } if (i > 1 && j > 0 && A[i] == B[j - 1] && A[i - 1] == B[j] && !arr.Contains(j - 1) && !arr.Contains(j)) { dp[i, j] = dp[i, j] || dp[i - 2, j - 2]; } if (j > 1) { dp[i, j] = dp[i, j] || (A[i] == B[j - 2] && A[i] == B[j - 1] && !arr.Contains(j - 2) && !arr.Contains(j - 1) && dp[i, j - 2]); } if (i > 1) { dp[i, j] = dp[i, j] || (A[i] == B[j] && A[i - 1] == B[j - 1] && !arr.Contains(j) && !arr.Contains(j - 1) && dp[i - 2, j - 1]); } } } return dp[N - 1, M - 1]; } static void Main() { string A = "abcabka" ; string B = "acbakba" ; List< int > arr = new List< int > { 0, 3, 6 }; if (IsPossible(A, B, arr)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
function isPossible(A, B, arr) { const N = A.length; const M = B.length; // Create a 2D boolean array to store if it is possible to // transform A[0...i] to B[0...j] with the given constraints const dp = new Array(N).fill(0).map(() => new Array(M).fill( false )); // Initialize dp[0][0] as true if A[0] == B[0] dp[0][0] = A[0] === B[0]; // Initialize dp[0][j] for j > 0 for (let j = 1; j < M; j++) { dp[0][j] = A[0] === B[j] && arr[0] !== j && dp[0][j - 1]; } // Initialize dp[i][0] for i > 0 for (let i = 1; i < N; i++) { dp[i][0] = A[i] === B[0] && arr[0] !== i && dp[i - 1][0]; } // Fill the remaining cells of the dp table for (let i = 1; i < N; i++) { for (let j = 1; j < M; j++) { dp[i][j] = false ; if (A[i] === B[j]) { dp[i][j] = dp[i][j] || dp[i - 1][j - 1]; } if (i > 1 && j > 0 && A[i] === B[j - 1] && A[i - 1] === B[j] && arr[j - 1] !== j && arr[j] !== j - 1) { dp[i][j] = dp[i][j] || dp[i - 2][j - 2]; } if (j > 1) { dp[i][j] = dp[i][j] || (A[i] === B[j - 2] && A[i] === B[j - 1] && arr[j - 2] !== j && arr[j - 1] !== j && dp[i][j - 2]); } if (i > 1) { dp[i][j] = dp[i][j] || (A[i] === B[j] && A[i - 1] === B[j - 1] && arr[j] !== j && arr[j - 1] !== j - 1 && dp[i - 2][j - 1]); } } } return dp[N - 1][M - 1]; } // Example usage const A = "abcabka" ; const B = "acbakba" ; const arr = [0, 3, 6]; if (isPossible(A, B, arr)) { console.log( "Yes" ); } else { console.log( "No" ); } |
Output
Yes
Time complexity: O(NM), where N is the length of string A and M is the length of string B.
Auxiliary Space: O(NM), to store the 2D boolean dp array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!