Given two strings str1 and str2, each of length N and consisting of lowercase English alphabets only, the task is to check if string str1 can be transformed to string str2 by performing the following operations any number of times.
- Choose a non-empty substring in str1 and sort it in-place lexicographically, to arrange the characters of the substring in non-decreasing order.
Examples :
Input: str1 = “hdecb”, str2 = “cdheb”
Output: Yes
Explanation:
Sorting the substring “ec” in str1 modifies the string to “hdceb”
Sorting the substring “hdc” in str1 modifies the string to “cdheb”.
Since, the modified string is same as str2, the answer is Yes.Input: str1 = “abcdef”, str2 = “dacbfe”
Output: No
Approach: Follow the steps below to solve the problem:
- Observe that, in the string str1, if there are two characters str1[i] and str2[j] such that str1[i] < str1[j], then these characters can be swapped.
- In other words, it is possible to move a character freely to the left, until it encounters a smaller character. For example, “acdb” can be converted to either “acbd“, “abcd” as ‘b‘ can be moved freely to the left until ‘a‘ occurs.
- Therefore, check if it is possible to move the required characters to the left, to their respective positions in the string str2.
- Store the indices of every character of string str1 in an array.
- Traverse the string str2, and for each character, check if the same character in str1 can be shifted to that position or not.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if str1 can be// transformed to t by sorting substringsvoid canTransform(string& s, string& t){ int n = s.length(); // Occur[i] stores the indices // of char ('a'+i) in string s vector<int> occur[26]; for (int x = 0; x < n; x++) { char ch = s[x] - 'a'; occur[ch].push_back(x); } // idx[i] stores the next available // index of char ('a'+i) in occur[i] vector<int> idx(26, 0); bool poss = true; for (int x = 0; x < n; x++) { char ch = t[x] - 'a'; // If this char is not available // anymore if (idx[ch] >= occur[ch].size()) { // Conversion not possible poss = false; break; } for (int small = 0; small < ch; small++) { // If one of the smaller characters // is available and occurs before if (idx[small] < occur[small].size() && occur[small][idx[small]] < occur[ch][idx[ch]]) { // Conversion not possible poss = false; break; } } idx[ch]++; } // Print the answer if (poss) { cout << "Yes" << endl; } else { cout << "No" << endl; }}// Driver Codeint main(){ string s, t; s = "hdecb"; t = "cdheb"; canTransform(s, t); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Function to check if str1 // can be transformed to t by // sorting subStringsstatic void canTransform(String s, String t){ int n = s.length(); // Occur[i] stores the indices // of char ('a'+i) in String s Vector<Integer> occur[] = new Vector[26]; for (int i = 0; i < occur.length; i++) occur[i] = new Vector<Integer>(); for (int x = 0; x < n; x++) { char ch = (char)(s.charAt(x) - 'a'); occur[ch].add(x); } // idx[i] stores the next available // index of char ('a'+i) in occur[i] int []idx = new int[26]; boolean poss = true; for (int x = 0; x < n; x++) { char ch = (char)(t.charAt(x) - 'a'); // If this char is // not available anymore if (idx[ch] >= occur[ch].size()) { // Conversion not possible poss = false; break; } for (int small = 0; small < ch; small++) { // If one of the smaller characters // is available and occurs before if (idx[small] < occur[small].size() && occur[small].get(idx[small]) < occur[ch].get(idx[ch])) { // Conversion not possible poss = false; break; } } idx[ch]++; } // Print the answer if (poss) { System.out.print("Yes" + "\n"); } else { System.out.print("No" + "\n"); }}// Driver Codepublic static void main(String[] args){ String s, t; s = "hdecb"; t = "cdheb"; canTransform(s, t);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approach# Function to check if str1 can be# transformed to t by sorting substringsdef canTransform(s, t): n = len(s) # Occur[i] stores the indices # of ('a'+i) in string s occur = [[] for i in range(26)] for x in range(n): ch = ord(s[x]) - ord('a') occur[ch].append(x) # idx[i] stores the next available # index of ('a'+i) in occur[i] idx = [0] * (26) poss = True for x in range(n): ch = ord(t[x]) - ord('a') # If this is not available # anymore if (idx[ch] >= len(occur[ch])): # Conversion not possible poss = False break for small in range(ch): # If one of the smaller characters # is available and occurs before if (idx[small] < len(occur[small]) and occur[small][idx[small]] < occur[ch][idx[ch]]): # Conversion not possible poss = False break idx[ch] += 1 # Print the answer if (poss): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': s = "hdecb" t = "cdheb" canTransform(s, t)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if str1 // can be transformed to t by // sorting subStringsstatic void canTransform(String s, String t){ int n = s.Length; // Occur[i] stores the indices // of char ('a'+i) in String s List<int> []occur = new List<int>[26]; for(int i = 0; i < occur.Length; i++) occur[i] = new List<int>(); for(int x = 0; x < n; x++) { char ch = (char)(s[x] - 'a'); occur[ch].Add(x); } // idx[i] stores the next available // index of char ('a'+i) in occur[i] int []idx = new int[26]; bool poss = true; for(int x = 0; x < n; x++) { char ch = (char)(t[x] - 'a'); // If this char is // not available anymore if (idx[ch] >= occur[ch].Count) { // Conversion not possible poss = false; break; } for(int small = 0; small < ch; small++) { // If one of the smaller characters // is available and occurs before if (idx[small] < occur[small].Count && occur[small][idx[small]] < occur[ch][idx[ch]]) { // Conversion not possible poss = false; break; } } idx[ch]++; } // Print the answer if (poss) { Console.Write("Yes" + "\n"); } else { Console.Write("No" + "\n"); }}// Driver Codepublic static void Main(String[] args){ String s, t; s = "hdecb"; t = "cdheb"; canTransform(s, t);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript Program to implement// the above approach// Function to check if str1 can be// transformed to t by sorting substringsfunction canTransform(s, t){ var n = s.length; // Occur[i] stores the indices // of char ('a'+i) in string s var occur = Array.from(Array(26), ()=>new Array()); for (var x = 0; x < n; x++) { var ch = s[x].charCodeAt(0) - 'a'.charCodeAt(0); occur[ch].push(x); } // idx[i] stores the next available // index of char ('a'+i) in occur[i] var idx = Array(26).fill(0); var poss = true; for (var x = 0; x < n; x++) { var ch = t[x].charCodeAt(0) - 'a'.charCodeAt(0); // If this char is not available // anymore if (idx[ch] >= occur[ch].length) { // Conversion not possible poss = false; break; } for (var small = 0; small < ch; small++) { // If one of the smaller characters // is available and occurs before if (idx[small] < occur[small].length && occur[small][idx[small]] < occur[ch][idx[ch]]) { // Conversion not possible poss = false; break; } } idx[ch]++; } // Print the answer if (poss) { document.write( "Yes" ); } else { document.write( "No" ); }}// Driver Codevar s, t;s = "hdecb";t = "cdheb";canTransform(s, t);</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
