Check if two strings can be made equal by swapping pairs of adjacent characters

0 0 19 minutes read

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 A₁ and A₂. Now the string becomes A = “acbabka”.
Swap A₄ and A₅. 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”.

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>

Output

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.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!