Encuentre la substring más larga con k caracteres únicos en una string dada

Dada una string, debe imprimir la substring más larga posible que tenga exactamente M caracteres únicos. Si hay más de una substring de la mayor longitud posible, imprima cualquiera de ellas.

Ejemplos: 

"aabbcc", k = 1
Max substring can be any one from {"aa" , "bb" , "cc"}.

"aabbcc", k = 2
Max substring can be any one from {"aabb" , "bbcc"}.

"aabbcc", k = 3
There are substrings with exactly 3 unique characters
{"aabbcc" , "abbcc" , "aabbc" , "abbc" }
Max is "aabbcc" with length 6.

"aaabbb", k = 3
There are only two unique characters, thus show error message. 

Fuente: pregunta de la entrevista de Google.

Método 1 (Fuerza bruta) 
Si la longitud de la string es n, entonces puede haber n*(n+1)/2 substrings posibles. Una forma simple es generar todas las substrings y verificar si cada una tiene exactamente k caracteres únicos o no. Si aplicamos esta fuerza bruta, se necesitaría O(n 2 ) para generar todas las substrings y O(n) para verificar cada una. Por lo tanto, en general sería O(n 3 ).
Podemos mejorar aún más esta solución creando una tabla hash y, al generar las substrings, verificar la cantidad de caracteres únicos que usan esa tabla hash. Así mejoraría hasta O(n 2 ).

Método 2 (Tiempo Lineal) 
El problema se puede resolver en O(n). La idea es mantener una ventana y agregar elementos a la ventana hasta que contenga menos o igual k, actualice nuestro resultado si es necesario mientras lo hace. Si los elementos únicos exceden los requeridos en la ventana, comience a eliminar los elementos del lado izquierdo. 
A continuación se muestran las implementaciones de lo anterior. Las implementaciones asumen que el alfabeto de string de entrada contiene solo 26 caracteres (de ‘a’ a ‘z’). El código se puede extender fácilmente a 256 caracteres. 

C++

// C++ program to find the longest substring with k unique
// characters in a given string
#include <iostream>
#include <cstring>
#define MAX_CHARS 26
using namespace std;
 
// This function calculates number of unique characters
// using a associative array count[]. Returns true if
// no. of characters are less than required else returns
// false.
bool isValid(int count[], int k)
{
    int val = 0;
    for (int i=0; i<MAX_CHARS; i++)
        if (count[i] > 0)
            val++;
 
    // Return true if k is greater than or equal to val
    return (k >= val);
}
 
// Finds the maximum substring with exactly k unique chars
void kUniques(string s, int k)
{
    int u = 0; // number of unique characters
    int n = s.length();
 
    // Associative array to store the count of characters
    int count[MAX_CHARS];
    memset(count, 0, sizeof(count));
 
    // Traverse the string, Fills the associative array
    // count[] and count number of unique characters
    for (int i=0; i<n; i++)
    {
        if (count[s[i]-'a']==0)
            u++;
        count[s[i]-'a']++;
    }
 
    // If there are not enough unique characters, show
    // an error message.
    if (u < k)
    {
        cout << "Not enough unique characters";
        return;
    }
 
    // Otherwise take a window with first element in it.
    // start and end variables.
    int curr_start = 0, curr_end = 0;
 
    // Also initialize values for result longest window
    int max_window_size = 1, max_window_start = 0;
 
    // Initialize associative array count[] with zero
    memset(count, 0, sizeof(count));
 
    count[s[0]-'a']++;  // put the first character
 
    // Start from the second character and add
    // characters in window according to above
    // explanation
    for (int i=1; i<n; i++)
    {
        // Add the character 's[i]' to current window
        count[s[i]-'a']++;
        curr_end++;
 
        // If there are more than k unique characters in
        // current window, remove from left side
        while (!isValid(count, k))
        {
            count[s[curr_start]-'a']--;
            curr_start++;
        }
 
        // Update the max window size if required
        if (curr_end-curr_start+1 > max_window_size)
        {
            max_window_size = curr_end-curr_start+1;
            max_window_start = curr_start;
        }
    }
 
    cout << "Max substring is : "
         << s.substr(max_window_start, max_window_size)
         << " with length " << max_window_size << endl;
}
 
// Driver function
int main()
{
    string s = "aabacbebebe";
    int k = 3;
    kUniques(s, k);
    return 0;
}

Java

import java.util.Arrays;
 
// Java program to find the longest substring with k unique
// characters in a given string
class GFG {
 
    final static int MAX_CHARS = 26;
 
   // This function calculates number
   // of unique characters
   // using a associative array
   // count[]. Returns true if
   // no. of characters are less
   // than required else returns
   // false.
    static boolean isValid(int count[],
                                   int k)
    {
        int val = 0;
        for (int i = 0; i < MAX_CHARS; i++)
        {
            if (count[i] > 0)
            {
                val++;
            }
        }
 
        // Return true if k is greater
        // than or equal to val
        return (k >= val);
    }
 
    // Finds the maximum substring
    // with exactly k unique chars
    static void kUniques(String s, int k)
    {
        int u = 0;
        int n = s.length();
 
        // Associative array to store
        // the count of characters
        int count[] = new int[MAX_CHARS];
        Arrays.fill(count, 0);
        // Traverse the string, Fills
        // the associative array
        // count[] and count number
        // of unique characters
        for (int i = 0; i < n; i++)
        {
            if (count[s.charAt(i) - 'a'] == 0)
            {
                u++;
            }
            count[s.charAt(i) - 'a']++;
        }
 
        // If there are not enough
        // unique characters, show
        // an error message.
        if (u < k) {
            System.out.print("Not enough unique characters");
            return;
        }
 
        // Otherwise take a window with
        // first element in it.
        // start and end variables.
        int curr_start = 0, curr_end = 0;
 
        // Also initialize values for
        // result longest window
        int max_window_size = 1;
        int max_window_start = 0;
 
        // Initialize associative
        // array count[] with zero
        Arrays.fill(count, 0);
         
        // put the first character
        count[s.charAt(0) - 'a']++;
 
        // Start from the second character and add
        // characters in window according to above
        // explanation
        for (int i = 1; i < n; i++) {
            // Add the character 's[i]'
            // to current window
            count[s.charAt(i) - 'a']++;
            curr_end++;
 
            // If there are more than k
            // unique characters in
            // current window, remove from left side
            while (!isValid(count, k)) {
                count[s.charAt(curr_start) - 'a']--;
                curr_start++;
            }
 
            // Update the max window size if required
            if (curr_end - curr_start + 1 > max_window_size)
            {
                max_window_size = curr_end - curr_start + 1;
                max_window_start = curr_start;
            }
        }
 
        System.out.println("Max substring is : "
                + s.substring(max_window_start,
                    max_window_start + max_window_size)
                + " with length " + max_window_size);
    }
 
    // Driver Code
    static public void main(String[] args) {
        String s = "aabacbebebe";
        int k = 3;
        kUniques(s, k);
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program to find the longest substring with k unique
# characters in a given string
MAX_CHARS = 26
 
# This function calculates number of unique characters
# using a associative array count[]. Returns true if
# no. of characters are less than required else returns
# false.
def isValid(count, k):
    val = 0
    for i in range(MAX_CHARS):
        if count[i] > 0:
            val += 1
 
    # Return true if k is greater than or equal to val
    return (k >= val)
 
# Finds the maximum substring with exactly k unique characters
def kUniques(s, k):
    u = 0 # number of unique characters
    n = len(s)
 
    # Associative array to store the count
    count = [0] * MAX_CHARS
 
    # Traverse the string, fills the associative array
    # count[] and count number of unique characters
    for i in range(n):
        if count[ord(s[i])-ord('a')] == 0:
            u += 1
        count[ord(s[i])-ord('a')] += 1
 
    # If there are not enough unique characters, show
    # an error message.
    if u < k:
        print ("Not enough unique characters")
        return
 
    # Otherwise take a window with first element in it.
    # start and end variables.
    curr_start = 0
    curr_end = 0
 
    # Also initialize values for result longest window
    max_window_size = 1
    max_window_start = 0
 
    # Initialize associative array count[] with zero
    count = [0] * len(count)
 
    count[ord(s[0])-ord('a')] += 1 # put the first character
 
    # Start from the second character and add
    # characters in window according to above
    # explanation
    for i in range(1,n):
 
        # Add the character 's[i]' to current window
        count[ord(s[i])-ord('a')] += 1
        curr_end+=1
 
        # If there are more than k unique characters in
        # current window, remove from left side
        while not isValid(count, k):
            count[ord(s[curr_start])-ord('a')] -= 1
            curr_start += 1
 
        # Update the max window size if required
        if curr_end-curr_start+1 > max_window_size:
            max_window_size = curr_end-curr_start+1
            max_window_start = curr_start
 
    print ("Max substring is : " + s[max_window_start:max_window_start  + max_window_size]
    + " with length " + str(max_window_size))
 
# Driver function
s = "aabacbebebe"
k = 3
kUniques(s, k)
 
# This code is contributed by BHAVYA JAIN

C#

// C# program to find the longest substring with k unique 
// characters in a given string 
using System;
public class GFG
{
 
  static int MAX_CHARS = 26;
 
  // This function calculates number 
  // of unique characters 
  // using a associative array 
  // count[]. Returns true if 
  // no. of characters are less 
  // than required else returns 
  // false. 
  static bool isValid(int[] count, 
                      int k) 
  { 
    int val = 0; 
    for (int i = 0; i < MAX_CHARS; i++) 
    { 
      if (count[i] > 0) 
      { 
        val++; 
      } 
    } 
 
    // Return true if k is greater
    // than or equal to val 
    return (k >= val); 
  } 
 
  // Finds the maximum substring 
  // with exactly k unique chars 
  static void kUniques(string s, int k) 
  { 
    int u = 0; 
    int n = s.Length; 
 
    // Associative array to store 
    // the count of characters 
    int[] count = new int[MAX_CHARS]; 
    Array.Fill(count, 0);
 
    // Traverse the string, Fills 
    // the associative array 
    // count[] and count number 
    // of unique characters 
    for (int i = 0; i < n; i++) 
    { 
      if (count[s[i] - 'a'] == 0) 
      { 
        u++; 
      } 
      count[s[i] - 'a']++; 
    } 
 
    // If there are not enough 
    // unique characters, show 
    // an error message. 
    if (u < k) { 
      Console.Write("Not enough unique characters"); 
      return; 
    } 
 
    // Otherwise take a window with
    // first element in it. 
    // start and end variables. 
    int curr_start = 0, curr_end = 0; 
 
    // Also initialize values for
    // result longest window 
    int max_window_size = 1;
    int max_window_start = 0; 
 
    // Initialize associative 
    // array count[] with zero 
    Array.Fill(count, 0); 
 
    // put the first character 
    count[s[0] - 'a']++; 
 
    // Start from the second character and add 
    // characters in window according to above 
    // explanation 
    for (int i = 1; i < n; i++)
    {
       
      // Add the character 's[i]' 
      // to current window 
      count[s[i] - 'a']++; 
      curr_end++; 
 
      // If there are more than k 
      // unique characters in 
      // current window, remove from left side 
      while (!isValid(count, k)) { 
        count[s[curr_start] - 'a']--; 
        curr_start++; 
      } 
 
      // Update the max window size if required 
      if (curr_end - curr_start + 1 > max_window_size) 
      { 
        max_window_size = curr_end - curr_start + 1; 
        max_window_start = curr_start; 
      } 
    } 
 
    Console.WriteLine("Max substring is : "+
                      s.Substring(max_window_start, max_window_size) +
                      " with length " + max_window_size); 
  } 
 
  // Driver code
  static public void Main (){
    string s = "aabacbebebe"; 
    int k = 3; 
    kUniques(s, k); 
  }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
 
// Javascript program to find the longest
// substring with k unique characters in
// a given string
let MAX_CHARS = 26;
 
// This function calculates number of
// unique characters using a associative
// array count[]. Returns true if no. of
// characters are less than required else
// returns false.
function isValid(count, k)
{
    let val = 0;
    for(let i = 0; i < MAX_CHARS; i++)
    {
        if (count[i] > 0)
        {
            val++;
        }
    }
 
    // Return true if k is greater
    // than or equal to val
    return (k >= val);
}
 
// Finds the maximum substring
// with exactly k unique chars
function kUniques(s,k)
{
     
    // Number of unique characters
    let u = 0;
    let n = s.length;
    let count = new Array(MAX_CHARS);
     
    for(let i = 0; i < MAX_CHARS; i++)
    {
        count[i] = 0;
    }
     
    // Traverse the string, Fills
    // the associative array
    // count[] and count number
    // of unique characters
    for(let i = 0; i < n; i++)
    {
        if (count[s[i].charCodeAt(0) -
                   'a'.charCodeAt(0)] == 0)
        {
            u++;
        }
        count[s[i].charCodeAt(0) -
              'a'.charCodeAt(0)]++;
    }
 
    // If there are not enough
    // unique characters, show
    // an error message.
    if (u < k)
    {
        document.write("Not enough unique characters");
        return;
    }
 
    // Otherwise take a window with
    // first element in it.
    // start and end variables.
    let curr_start = 0, curr_end = 0;
 
    // Also initialize values for
    // result longest window
    let max_window_size = 1;
    let max_window_start = 0;
 
    // Initialize associative
    // array count[] with zero
    for(let i = 0; i < MAX_CHARS; i++)
    {
        count[i] = 0;
    }
     
    // put the first character
    count[s[0].charCodeAt(0) -
           'a'.charCodeAt(0)]++;
 
    // Start from the second character and add
    // characters in window according to above
    // explanation
    for(let i = 1; i < n; i++)
    {
         
        // Add the character 's[i]'
        // to current window
        count[s[i].charCodeAt(0) -
               'a'.charCodeAt(0)]++;
        curr_end++;
 
        // If there are more than k
        // unique characters in
        // current window, remove from left side
        while (!isValid(count, k))
        {
            count[s[curr_start].charCodeAt(0) -
                            'a'.charCodeAt(0)]--;
            curr_start++;
        }
 
        // Update the max window size if required
        if (curr_end - curr_start + 1 > max_window_size)
        {
            max_window_size = curr_end - curr_start + 1;
            max_window_start = curr_start;
        }
    }
 
    document.write("Max substring is : " +
                   s.substring(max_window_start,
                   max_window_start +
                   max_window_size + 1) +
                   " with length " + max_window_size);
}
 
// Driver Code
let s = "aabacbebebe";
let k = 3;
 
kUniques(s, k);
 
// This code is contributed by rag2127
 
</script>

Producción: 

Max substring is : cbebebe with length 7

Complejidad de tiempo: considerando que la función «isValid()» toma un tiempo constante, la complejidad de tiempo de la solución anterior es O (n).
Este artículo es una contribución de Gaurav Sharma . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *