La string lexicográficamente más corta de longitud como máximo K que no es una substring de la String dada

Dada una string S , la tarea es encontrar la string lexicográficamente más corta de longitud menor o igual a K que no sea una substring de la string dada . Si no es posible, imprima -1.

Ejemplos:

Entrada: S = zxabcehgf, K = 2
Salida: d
Explicación: Lexicográficamente, la string más corta que no es una substring de una string determinada es d.

Entrada: S = sdhaacbdefghijklmnopqrstuvwxyz, K = 3
Salida: ab

Enfoque: el problema se puede resolver encontrando todas las substrings de la string dada S que tienen una longitud menor o igual que K . Luego comience desde la string lexicográficamente más pequeña ‘ a ‘, y siga formando la siguiente string hasta que no encontremos la respuesta. Siga los pasos a continuación para resolver el problema.

• Inicialice un conjunto de strings , digamos st , para almacenar todas las substrings de longitud como máximo K.
• Iterar de 1 a K para crear todas las strings de longitudes posibles de 1 a K.
• Compruebe si la string actual formada está presente en el conjunto o no. Si no, imprímelo y devuélvelo.
• De lo contrario, forme la siguiente string lexicográfica y repita el proceso hasta encontrar una respuesta .

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

// C++ implementation for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return a set of all
// substrings of given string which have
// length less than or equal to k
set<string> presentSubstring(string s, int k)
{
    set<string> st;
    int n = s.length();
 
    for (int i = 0; i < n; i++) {
        string s1 = "";
 
        for (int j = 0; j < k && i + j < n; j++) {
            s1.push_back(s[i + j]);
 
            st.insert(s1);
        }
    }
 
    return st;
}
 
// Function to print the lexicographically
// smallest substring of length atmost k
// which is not present in given string s
string smallestSubstring(string s, int k)
{
    set<string> st;
 
    // All substrings of length atmost k
    // present in string s are stored in
    // this set
    st = presentSubstring(s, k);
 
    int index;
 
    // Loop to change length of substring
    for (int len = 1; len <= k; len++) {
 
        // String with length=len which has
        // all characters as 'a'
        string t(len, 'a');
 
        while (true) {
 
            // If the substrings set does
            // not contain this string then
            // we have found the answer
            if (st.count(t) == 0) {
                return t;
            }
 
            index = len - 1;
 
            // Changing the likes of 'azz'
            // and 'daz' to 'baa' and 'dba'
            // respectively
            while (index >= 0 && t[index] == 'z') {
                t[index] = 'a';
                index--;
            }
 
            if (index >= 0)
                t[index]++;
 
            // Reached a string like 'zz'
            // or 'zzz' increase the length
            // of the substring
            else
                break;
        }
    }
    return "-1";
}
 
// Driver Code
int main()
{
 
    // Given Input
    string s = "sdhaacbdefghijklmnopqrstuvwxyz";
    int K = 3;
 
    // Function Call
    cout << smallestSubstring(s, K) << endl;
 
    return 0;
}

// Java implementation for above approach
import java.util.*;
 
class GFG
{
 
// Function to return a set of all
// subStrings of given String which have
// length less than or equal to k
static HashSet<String> presentSubString(String s, int k)
{
    HashSet<String> st = new HashSet<String>();
    int n = s.length();
 
    for (int i = 0; i < n; i++) {
        String s1 = "";
 
        for (int j = 0; j < k && i + j < n; j++) {
            s1 += s.charAt(i + j);
 
            st.add(s1);
        }
    }
 
    return st;
}
 
// Function to print the lexicographically
// smallest subString of length atmost k
// which is not present in given String s
static String smallestSubString(String s, int k)
{
    HashSet<String> st = new HashSet<String>();
 
    // All subStrings of length atmost k
    // present in String s are stored in
    // this set
    st = presentSubString(s, k);
 
    int index;
 
    // Loop to change length of subString
    for (int len = 1; len <= k; len++) {
 
        // String with length=len which has
        // all characters as 'a'
        String t = "";
        for(int i=0;i<len;i++)
            t+='a';
 
        while (true) {
 
            // If the subStrings set does
            // not contain this String then
            // we have found the answer
            if (!st.contains(t)) {
                return t;
            }
 
            index = len - 1;
 
            // Changing the likes of 'azz'
            // and 'daz' to 'baa' and 'dba'
            // respectively
            while (index >= 0 && t.charAt(index) == 'z') {
                t=t.substring(0,index)+'a'+t.substring(index+1);
                index--;
            }
             
            if (index >= 0)
                t=t.substring(0,index)+ (char)((t.charAt(index))+1) + t.substring(index+1);
 
            // Reached a String like 'zz'
            // or 'zzz' increase the length
            // of the subString
            else
                break;
        }
    }
    return "-1";
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given Input
    String s = "sdhaacbdefghijklmnopqrstuvwxyz";
    int K = 3;
 
    // Function Call
    System.out.print(smallestSubString(s, K) +"\n");
}
}
 
// This code is contributed by shikhasingrajput

# Python 3 implementation for above approach
 
# Function to return a set of all
# substrings of given string which have
# length less than or equal to k
def presentSubstring(s, k):
    st = set()
    n = len(s)
    s = list(s)
 
    for i in range(n):
        s1 = ""
        j = 0
        while(j < k and i + j < n):
            s1 += s[i + j]
 
            st.add(s1)
            j += 1
     
    s = ''.join(s)
    return st
 
# Function to print the lexicographically
# smallest substring of length atmost k
# which is not present in given string s
def smallestSubstring(s, k):
    st = set()
 
    # All substrings of length atmost k
    # present in string s are stored in
    # this set
    st = presentSubstring(s, k)
 
    index = 0
 
    # Loop to change length of substring
    for len1 in range(1,k+1,1):
        # String with length=len which has
        # all characters as 'a'
        t = []
        for x in range(len1):
            t.append('a')
 
        while (True):
            # If the substrings set does
            # not contain this string then
            # we have found the answer
            if (''.join(t) not in st):
                return ''.join(t)
 
            index = len1 - 1
 
            # Changing the likes of 'azz'
            # and 'daz' to 'baa' and 'dba'
            # respectively
            while (index >= 0 and t[index] == 'z'):
                t[index] = 'a'
                index -= 1
 
            if (index >= 0):
                t[index] = chr(ord(t[index])+1)
 
            # Reached a string like 'zz'
            # or 'zzz' increase the length
            # of the substring
            else:
                break
    return "-1"
 
# Driver Code
if __name__ == '__main__':
    # Given Input
    s = "sdhaacbdefghijklmnopqrstuvwxyz"
    K = 3
 
    # Function Call
    print(smallestSubstring(s, K))
     
    # This code is contributed by ipg2016107.

// C# implementation for above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to return a set of all
    // substrings of given string which have
    // length less than or equal to k
    static HashSet<string> presentSubstring(string s, int k)
    {
        HashSet<string> st = new HashSet<string>();
        int n = s.Length;
 
        for (int i = 0; i < n; i++) {
            string s1 = "";
 
            for (int j = 0; j < k && i + j < n; j++) {
                s1 += s[i + j];
 
                st.Add(s1);
            }
        }
 
        return st;
    }
 
    // Function to print the lexicographically
    // smallest substring of length atmost k
    // which is not present in given string s
    static string smallestSubstring(string s, int k)
    {
        HashSet<string> st = new HashSet<string>();
 
        // All substrings of length atmost k
        // present in string s are stored in
        // this set
        st = presentSubstring(s, k);
 
        int index;
 
        // Loop to change length of substring
        for (int len = 1; len <= k; len++) {
 
            // String with length=len which has
            // all characters as 'a'
            string t = "";
            for (int i = 0; i < len; i++)
                t += 'a';
 
            while (true) {
 
                // If the substrings set does
                // not contain this string then
                // we have found the answer
                if (st.Contains(t)==false) {
                    return t;
                }
 
                index = len - 1;
 
                // Changing the likes of 'azz'
                // and 'daz' to 'baa' and 'dba'
                // respectively
                while (index >= 0 && t[index] == 'z') {
                    t = t.Substring(0, index) + 'a'
                        + t.Substring(index + 1);
                    index--;
                }
 
                if (index >= 0) {
                    t = t.Substring(0, index)
                        + Convert.ToChar((int)t[index] + 1)
                        + t.Substring(index + 1);
                }
 
                // Reached a string like 'zz'
                // or 'zzz' increase the length
                // of the substring
                else
                    break;
            }
           // t += 'b';
        }
        return "-1";
    }
 
    // Driver Code
    public static void Main()
    {
 
        // Given Input
        string s = "sdhaacbdefghijklmnopqrstuvwxyz";
        int K = 3;
 
        // Function Call
        Console.Write(smallestSubstring(s, K));
    }
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript implementation for above approach
 
// Function to return a set of all
// substrings of given string which have
// length less than or equal to k
function presentSubstring(s, k) {
  let st = new Set();
  let n = s.length;
  s = s.split("");
 
  for (let i = 0; i < n; i++) {
    let s1 = "";
 
    for (let j = 0; j < k && i + j < n; j++) {
      s1 += s[i + j];
 
      st.add(s1);
    }
  }
 
  return st;
}
 
// Function to print the lexicographically
// smallest substring of length atmost k
// which is not present in given string s
function smallestSubstring(s, k) {
  let st = new Set();
 
  // All substrings of length atmost k
  // present in string s are stored in
  // this set
  st = presentSubstring(s, k);
 
  let index = 0;
 
  // Loop to change length of substring
  for (let len = 1; len <= k; len++)
  {
   
    // String with length=len which has
    // all characters as 'a'
    let t = new Array(len).fill("a");
 
    while (true)
    {
     
      // If the substrings set does
      // not contain this string then
      // we have found the answer
 
      if (!st.has(t.join(""))) {
        return t.join("");
      }
 
      index = len - 1;
 
      // Changing the likes of 'azz'
      // and 'daz' to 'baa' and 'dba'
      // respectively
      while (index >= 0 && t[index] == "z") {
        t[index] = "a";
        index--;
      }
 
      if (index >= 0)
        t[index] = String.fromCharCode(t[index].charCodeAt(0) + 1);
         
      // Reached a string like 'zz'
      // or 'zzz' increase the length
      // of the substring
      else break;
    }
  }
  return "-1";
}
 
// Driver Code
 
// Given Input
let s = "sdhaacbdefghijklmnopqrstuvwxyz";
let K = 3;
 
// Function Call
document.write(smallestSubstring(s, K));
 
// This code is contributed by _saurabh_jaiswal.
</script>

ab

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