Dada una string str y un entero K , la tarea es imprimir la longitud de la substring más larga posible que tenga exactamente K caracteres únicos. Si hay más de una substring de la mayor longitud posible, imprima cualquiera de ellas o imprima -1 si no existe tal substring posible.
Ejemplos:
Entrada: str = “aabacbebebe”, K = 3
Salida: 7
“cbebebe” es la substring requerida.Entrada: str = “aabc”, K = 4
Salida: -1
Enfoque: En este artículo se ha discutido un enfoque para resolver este problema . En este artículo, se discutirá un enfoque basado en la búsqueda binaria . La búsqueda binaria se aplicará a la longitud de la substring que tenga al menos K caracteres únicos. Digamos que intentamos con la longitud len y verificamos si hay una substring de tamaño len que tenga al menos k caracteres únicos. Si es posible, intente maximizar el tamaño buscando esta longitud hasta la longitud máxima posible, es decir, el tamaño de la string de entrada. Si no es posible, busque una lente de menor tamaño.
Para verificar que la longitud dada por la búsqueda binaria tendrá k caracteres únicos, se puede usar un conjunto para insertar todos los caracteres, y luego, si el tamaño del conjunto es menor que k, entonces la respuesta no es posible, de lo contrario, la respuesta dada por la búsqueda binaria es la respuesta máxima.
La búsqueda binaria es aplicable aquí porque se sabe si para algún len la respuesta es posible y queremos maximizar el len para que el dominio de búsqueda cambie y busquemos desde este len hasta n.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if there
// is a substring of length len
// with <=k unique characters
bool isValidLen(string s, int len, int k)
{
// Size of the string
int n = s.size();
// Map to store the characters
// and their frequency
unordered_map<char, int> mp;
int right = 0;
// Update the map for the
// first substring
while (right < len) {
mp[s[right]]++;
right++;
}
if (mp.size() <= k)
return true;
// Check for the rest of the substrings
while (right < n) {
// Add the new character
mp[s[right]]++;
// Remove the first character
// of the previous window
mp[s[right - len]]--;
// Update the map
if (mp[s[right - len]] == 0)
mp.erase(s[right - len]);
if (mp.size() <= k)
return true;
right++;
}
return mp.size() <= k;
}
// Function to return the length of the
// longest substring which has K
// unique characters
int maxLenSubStr(string s, int k)
{
// Check if the complete string
// contains K unique characters
set<char> uni;
for (auto x : s)
uni.insert(x);
if (uni.size() < k)
return -1;
// Size of the string
int n = s.size();
// Apply binary search
int lo = -1, hi = n + 1;
while (hi - lo > 1) {
int mid = lo + hi >> 1;
if (isValidLen(s, mid, k))
lo = mid;
else
hi = mid;
}
return lo;
}
// Driver code
int main()
{
string s = "aabacbebebe";
int k = 3;
cout << maxLenSubStr(s, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true if there
// is a subString of length len
// with <=k unique characters
static boolean isValidLen(String s,
int len, int k)
{
// Size of the String
int n = s.length();
// Map to store the characters
// and their frequency
Map<Character,
Integer> mp = new HashMap<Character,
Integer>();
int right = 0;
// Update the map for the
// first subString
while (right < len)
{
if (mp.containsKey(s.charAt(right)))
{
mp.put(s.charAt(right),
mp.get(s.charAt(right)) + 1);
}
else
{
mp.put(s.charAt(right), 1);
}
right++;
}
if (mp.size() <= k)
return true;
// Check for the rest of the subStrings
while (right < n)
{
// Add the new character
if (mp.containsKey(s.charAt(right)))
{
mp.put(s.charAt(right),
mp.get(s.charAt(right)) + 1);
}
else
{
mp.put(s.charAt(right), 1);
}
// Remove the first character
// of the previous window
if (mp.containsKey(s.charAt(right - len)))
{
mp.put(s.charAt(right - len),
mp.get(s.charAt(right - len)) - 1);
}
// Update the map
if (mp.get(s.charAt(right - len)) == 0)
mp.remove(s.charAt(right - len));
if (mp.size() <= k)
return true;
right++;
}
return mp.size() <= k;
}
// Function to return the length of the
// longest subString which has K
// unique characters
static int maxLenSubStr(String s, int k)
{
// Check if the complete String
// contains K unique characters
Set<Character> uni = new HashSet<Character>();
for (Character x : s.toCharArray())
uni.add(x);
if (uni.size() < k)
return -1;
// Size of the String
int n = s.length();
// Apply binary search
int lo = -1, hi = n + 1;
while (hi - lo > 1)
{
int mid = lo + hi >> 1;
if (isValidLen(s, mid, k))
lo = mid;
else
hi = mid;
}
return lo;
}
// Driver code
public static void main(String[] args)
{
String s = "aabacbebebe";
int k = 3;
System.out.print(maxLenSubStr(s, k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function that returns True if there # is a sub of length len # with <=k unique characters def isValidLen(s, lenn, k): # Size of the n = len(s) # Map to store the characters # and their frequency mp = dict() right = 0 # Update the map for the # first sub while (right < lenn): mp[s[right]] = mp.get(s[right], 0) + 1 right += 1 if (len(mp) <= k): return True # Check for the rest of the subs while (right < n): # Add the new character mp[s[right]] = mp.get(s[right], 0) + 1 # Remove the first character # of the previous window mp[s[right - lenn]] -= 1 # Update the map if (mp[s[right - lenn]] == 0): del mp[s[right - lenn]] if (len(mp) <= k): return True right += 1 return len(mp)<= k # Function to return the length of the # longest sub which has K # unique characters def maxLenSubStr(s, k): # Check if the complete # contains K unique characters uni = dict() for x in s: uni[x] = 1 if (len(uni) < k): return -1 # Size of the n = len(s) # Apply binary search lo = -1 hi = n + 1 while (hi - lo > 1): mid = lo + hi >> 1 if (isValidLen(s, mid, k)): lo = mid else: hi = mid return lo # Driver code s = "aabacbebebe" k = 3 print(maxLenSubStr(s, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function that returns true if there
// is a subString of length len
// with <=k unique characters
static bool isValidLen(String s,
int len, int k)
{
// Size of the String
int n = s.Length;
// Map to store the characters
// and their frequency
Dictionary<char,
int> mp = new Dictionary<char,
int>();
int right = 0;
// Update the map for the
// first subString
while (right < len)
{
if (mp.ContainsKey(s[right]))
{
mp[s[right]] = mp[s[right]] + 1;
}
else
{
mp.Add(s[right], 1);
}
right++;
}
if (mp.Count <= k)
return true;
// Check for the rest of the subStrings
while (right < n)
{
// Add the new character
if (mp.ContainsKey(s[right]))
{
mp[s[right]] = mp[s[right]] + 1;
}
else
{
mp.Add(s[right], 1);
}
// Remove the first character
// of the previous window
if (mp.ContainsKey(s[right - len]))
{
mp[s[right - len]] = mp[s[right - len]] - 1;
}
// Update the map
if (mp[s[right - len]] == 0)
mp.Remove(s[right - len]);
if (mp.Count <= k)
return true;
right++;
}
return mp.Count <= k;
}
// Function to return the length of the
// longest subString which has K
// unique characters
static int maxLenSubStr(String s, int k)
{
// Check if the complete String
// contains K unique characters
HashSet<char> uni = new HashSet<char>();
foreach (char x in s.ToCharArray())
uni.Add(x);
if (uni.Count < k)
return -1;
// Size of the String
int n = s.Length;
// Apply binary search
int lo = -1, hi = n + 1;
while (hi - lo > 1)
{
int mid = lo + hi >> 1;
if (isValidLen(s, mid, k))
lo = mid;
else
hi = mid;
}
return lo;
}
// Driver code
public static void Main(String[] args)
{
String s = "aabacbebebe";
int k = 3;
Console.Write(maxLenSubStr(s, k));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if there
// is a substring of length len
// with <=k unique characters
function isValidLen(s, len, k)
{
// Size of the string
var n = s.length;
// Map to store the characters
// and their frequency
var mp = new Map();
var right = 0;
// Update the map for the
// first substring
while (right < len) {
if(mp.has(s[right]))
mp.set(s[right],mp.get(s[right])+1)
else
mp.set(s[right], 1)
right++;
}
if (mp.size <= k)
return true;
// Check for the rest of the substrings
while (right < n) {
// Add the new character
if(mp.has(s[right]))
mp.set(s[right],mp.get(s[right])+1)
else
mp.set(s[right], 1)
// Remove the first character
// of the previous window
if(mp.has(s[right - len]))
mp.set(s[right - len], mp.get(s[right - len])-1)
// Update the map
if(mp.has(s[right - len]) && mp.get(s[right - len])==0)
mp.delete(s[right - len]);
if (mp.size <= k)
return true;
right++;
}
return mp.size <= k;
}
// Function to return the length of the
// longest substring which has K
// unique characters
function maxLenSubStr(s, k)
{
// Check if the complete string
// contains K unique characters
var uni = new Set();
s.split('').forEach(x => {
uni.add(x);
});
if (uni.size < k)
return -1;
// Size of the string
var n = s.length;
// Apply binary search
var lo = -1, hi = n + 1;
while (hi - lo > 1) {
var mid = lo + hi >> 1;
if (isValidLen(s, mid, k))
lo = mid;
else
hi = mid;
}
return lo;
}
// Driver code
var s = "aabacbebebe";
var k = 3;
document.write( maxLenSubStr(s, k));
</script>
Producción:
7