Compruebe si una string se puede transformar en otra ordenando substrings

Dadas dos strings str1 y str2, cada una de longitud N y que consisten solo en alfabetos ingleses en minúsculas, la tarea es verificar si la string str1 se puede transformar en la string str2 realizando las siguientes operaciones cualquier cantidad de veces.

• Elija una substring que no esté vacía en str1 y ordénela lexicográficamente en su lugar , para organizar los caracteres de la substring en orden no decreciente.

Ejemplos: 

Entrada: str1 = “hdecb”, str2 = “cdheb”
Salida: Sí
Explicación:
Ordenar la substring “ec” en str1 modifica la string a “hdceb”
Ordenar la substring “hdc” en str1 modifica la string a “cdheb”. 
Dado que la string modificada es la misma que str2, la respuesta es Sí. 

Entrada: str1 = “abcdef”, str2 = “dacbfe”
Salida: No

Enfoque: siga los pasos a continuación para resolver el problema:

• Observe que, en la string str1 , si hay dos caracteres str1[i] y str2[j] tales que str1[i] < str1[j] , entonces estos caracteres se pueden intercambiar.
• En otras palabras, es posible mover un personaje libremente hacia la izquierda, hasta que se encuentre con un personaje más pequeño. Por ejemplo, «acdb» se puede convertir en » acbd «, » abcd «, ya que ‘ b ‘ se puede mover libremente hacia la izquierda hasta que aparezca ‘ a ‘.
• Por lo tanto, verifique si es posible mover los caracteres requeridos a la izquierda, a sus respectivas posiciones en la string str2 .
• Almacene los índices de cada carácter de la string str1 en una array.
• Recorra la string str2 y, para cada carácter, verifique si el mismo carácter en str1 se puede desplazar a esa posición o no.

A continuación se muestra la implementación del enfoque anterior:

// 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 substrings
void 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 Code
int main()
{
    string s, t;
 
    s = "hdecb";
    t = "cdheb";
 
    canTransform(s, t);
    return 0;
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to check if str1
// can be transformed to t by
// sorting subStrings
static 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 Code
public static void main(String[] args)
{
  String s, t;
  s = "hdecb";
  t = "cdheb";
  canTransform(s, t);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to implement
# the above approach
 
# Function to check if str1 can be
# transformed to t by sorting substrings
def 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 Code
if __name__ == '__main__':
 
    s = "hdecb"
    t = "cdheb"
 
    canTransform(s, t)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if str1
// can be transformed to t by
// sorting subStrings
static 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 Code
public static void Main(String[] args)
{
  String s, t;
  s = "hdecb";
  t = "cdheb";
   
  canTransform(s, t);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript Program to implement
// the above approach
 
// Function to check if str1 can be
// transformed to t by sorting substrings
function 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 Code
var s, t;
s = "hdecb";
t = "cdheb";
canTransform(s, t);
 
</script>

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(N)