Given two strings X and Y of length N, the task is to check if both the strings can be made equal by reversing any substring of X exactly once. If it is possible, then print “Yes”. Otherwise, print “No”.
Examples:
Input: X = “adcbef”, Y = “abcdef”
Output: Yes
Explanation: Strings can be made equal by reversing the substring “dcb” of string X.Input: X = “126543”, Y = “123456”
Output: Yes
Explanation: Strings can be made equal by reversing the substring “6543” of string X.
Brute Force Approach:
The brute force approach to solve this problem would be to try every possible substring of X and reverse it, and then check if the reversed substring when replaced in X makes it equal to Y.
The steps for this approach are:
- Iterate through every substring of X.
- Reverse the substring and replace it in X.
- Check if the modified X is equal to Y. If it is, print “Yes” and return from the function.
- If the modified X is not equal to Y after iterating through all the substrings, 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 check if the strings// can be made equal or not by// reversing a substring of Xbool checkString(string X, string Y){ int n = X.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { reverse(X.begin() + i, X.begin() + j + 1); if (X == Y) { cout << "Yes" << endl; return true; } reverse(X.begin() + i, X.begin() + j + 1); } } cout << "No" << endl; return false;}// Driver Codeint main(){ string X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y); return 0;} |
Java
import java.util.*;public class Main { // Function to check if the strings // can be made equal or not by // reversing a substring of X static boolean checkString(String X, String Y) { int n = X.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { X = reverse(X, i, j); if (X.equals(Y)) { System.out.println("Yes"); return true; } X = reverse(X, i, j); } } System.out.println("No"); return false; } // Utility function to reverse the characters // in the substring of the given string static String reverse(String s, int start, int end) { char[] arr = s.toCharArray(); while (start < end) { char temp = arr[start]; arr[start++] = arr[end]; arr[end--] = temp; } return String.valueOf(arr); } // Driver Code public static void main(String[] args) { String X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y); }} |
Python3
# Function to check if the strings# can be made equal or not by# reversing a substring of Xdef checkString(X: str, Y: str) -> bool: n = len(X) for i in range(n): for j in range(i, n): X = X[:i] + X[i:j+1][::-1] + X[j+1:] if X == Y: print("Yes") return True X = X[:i] + X[i:j+1][::-1] + X[j+1:] print("No") return False# Driver Codeif __name__ == '__main__': X = "adcbef" Y = "abcdef" # Function Call checkString(X, Y) |
C#
// C# program for the above approachusing System;class Program{ // Function to check if the strings // can be made equal or not by // reversing a substring of X static bool CheckString(string X, string Y) { int n = X.Length; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { char[] arr = X.ToCharArray(); Array.Reverse(arr, i, j - i + 1); string modifiedX = new string(arr); if (modifiedX == Y) { Console.WriteLine("Yes"); return true; } Array.Reverse(arr, i, j - i + 1); } } Console.WriteLine("No"); return false; } // Driver Code static void Main(string[] args) { string X = "adcbef", Y = "abcdef"; // Function Call CheckString(X, Y); }} |
Javascript
// Function to check if the strings // can be made equal or not by // reversing a substring of X function checkString(X, Y) { let n = X.length; for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { let reversed = X.slice(i, j + 1).split('').reverse().join(''); let newX = X.slice(0, i) + reversed + X.slice(j + 1); if (newX === Y) { console.log("Yes"); return true; } } } console.log("No"); return false;}// Driver Codelet X = "adcbef";let Y = "abcdef";checkString(X, Y); |
Output
Yes
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, follow the steps below to solve the problem:
- Initialize a variable, say L as -1, to store the first index from the left having unequal characters in the two strings.
- Traverse the string X over the range [0, N – 1] using a variable i and if for any index, if the characters in the two strings are found to be unequal, set L = i and break out of the loop.
- Initialize a variable, say R as -1, to store the first index from the right having unequal characters in the two strings.
- Traverse the string X over the range [N – 1, 0] using the variable i and if for any index, if the characters in the two strings are found to be unequal, set R = i and break out of the loop.
- Reverse the characters of the string X over the indices [L, R].
- After completing the above steps, check if both the strings are equal or not. If found to be equal, then 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 check if the strings// can be made equal or not by// reversing a substring of Xbool checkString(string X, string Y){ // Store the first index from // the left which contains unequal // characters in both the strings int L = -1; // Store the first element from // the right which contains unequal // characters in both the strings int R = -1; // Checks for the first index from // left in which characters in both // the strings are unequal for (int i = 0; i < X.length(); ++i) { if (X[i] != Y[i]) { // Store the current index L = i; // Break out of the loop break; } } // Checks for the first index from // right in which characters in both // the strings are unequal for (int i = X.length() - 1; i > 0; --i) { if (X[i] != Y[i]) { // Store the current index R = i; // Break out of the loop break; } } // Reverse the substring X[L, R] reverse(X.begin() + L, X.begin() + R + 1); // If X and Y are equal if (X == Y) { cout << "Yes"; } // Otherwise else { cout << "No"; }}// Driver Codeint main(){ string X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if the Strings// can be made equal or not by// reversing a subString of Xstatic void checkString(String X, String Y){ // Store the first index from // the left which contains unequal // characters in both the Strings int L = -1; // Store the first element from // the right which contains unequal // characters in both the Strings int R = -1; // Checks for the first index from // left in which characters in both // the Strings are unequal for (int i = 0; i < X.length(); ++i) { if (X.charAt(i) != Y.charAt(i)) { // Store the current index L = i; // Break out of the loop break; } } // Checks for the first index from // right in which characters in both // the Strings are unequal for (int i = X.length() - 1; i > 0; --i) { if (X.charAt(i) != Y.charAt(i)) { // Store the current index R = i; // Break out of the loop break; } } // Reverse the subString X[L, R] X = X.substring(0, L) + reverse(X.substring(L, R + 1)) + X.substring(R + 1); // If X and Y are equal if (X.equals(Y)) { System.out.print("Yes"); } // Otherwise else { System.out.print("No"); }}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver Codepublic static void main(String[] args){ String X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to check if the strings# can be made equal or not by# reversing a substring of Xdef checkString(X, Y): # Store the first index from # the left which contains unequal # characters in both the strings L = -1 # Store the first element from # the right which contains unequal # characters in both the strings R = -1 # Checks for the first index from # left in which characters in both # the strings are unequal for i in range(len(X)): if (X[i] != Y[i]): # Store the current index L = i # Break out of the loop break # Checks for the first index from # right in which characters in both # the strings are unequal for i in range(len(X) - 1, 0, -1): if (X[i] != Y[i]): # Store the current index R = i # Break out of the loop break X = list(X) X = X[:L] + X[R : L - 1 : -1 ] + X[R + 1:] # If X and Y are equal if (X == list(Y)): print("Yes") # Otherwise else: print("No")# Driver Codeif __name__ == "__main__" : X = "adcbef" Y = "abcdef" # Function Call checkString(X, Y) # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{// Function to check if the Strings// can be made equal or not by// reversing a subString of Xstatic void checkString(String X, String Y){ // Store the first index from // the left which contains unequal // characters in both the Strings int L = -1; // Store the first element from // the right which contains unequal // characters in both the Strings int R = -1; // Checks for the first index from // left in which characters in both // the Strings are unequal for(int i = 0; i < X.Length; ++i) { if (X[i] != Y[i]) { // Store the current index L = i; // Break out of the loop break; } } // Checks for the first index from // right in which characters in both // the Strings are unequal for(int i = X.Length - 1; i > 0; --i) { if (X[i] != Y[i]) { // Store the current index R = i; // Break out of the loop break; } } // Reverse the subString X[L, R] X = X.Substring(0, L) + reverse(X.Substring(L, R + 1 - L)) + X.Substring(R + 1); // If X and Y are equal if (X.Equals(Y)) { Console.Write("Yes"); } // Otherwise else { Console.Write("No"); }}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for(l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver Codepublic static void Main(String[] args){ String X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function to check if the Strings // can be made equal or not by // reversing a subString of X function checkString(X, Y) { // Store the first index from // the left which contains unequal // characters in both the Strings var L = -1; // Store the first element from // the right which contains unequal // characters in both the Strings var R = -1; // Checks for the first index from // left in which characters in both // the Strings are unequal for (var i = 0; i < X.length; ++i) { if (X[i] !== Y[i]) { // Store the current index L = i; // Break out of the loop break; } } // Checks for the first index from // right in which characters in both // the Strings are unequal for (var i = X.length - 1; i > 0; --i) { if (X[i] !== Y[i]) { // Store the current index R = i; // Break out of the loop break; } } // Reverse the subString X[L, R] X = X.substring(0, L) + reverse(X.substring(L, R + 1)) + X.substring(R + 1); // If X and Y are equal if (X === Y) { document.write("Yes"); } // Otherwise else { document.write("No"); } } function reverse(input) { var a = input.split(""); var l, r = a.length - 1; for (l = 0; l < r; l++, r--) { var temp = a[l]; a[l] = a[r]; a[r] = temp; } return a.join(""); } // Driver Code var X = "adcbef", Y = "abcdef"; // Function Call checkString(X, Y); </script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
