Dada una string de longitud N, encuentre la longitud de la substring más pequeña que consta de un máximo de caracteres distintos. Nota: Nuestra salida puede tener el mismo carácter.
Ejemplos:
Input : "AABBBCBB" Output : 5 Input : "AABBBCBBAC" Output : 3 Explanation : Sub-string -> "BAC" Input : "GEEKSGEEKSFOR" Output : 8 Explanation : Sub-string -> "GEEKSFOR"
Método 1 (Fuerza bruta)
Podemos considerar todas las substrings una por una y verificar para cada substring ambas condiciones juntas
- los caracteres distintos de la substring son iguales al máximo de caracteres distintos
- la longitud de la substring debe ser mínima.
Implementación:
C++
/* C++ program to find the length of the smallest
substring consisting of maximum distinct characters */
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
// Find maximum distinct characters in any string
int max_distinct_char(string str, int n){
// Initialize all character's count with 0
int count[NO_OF_CHARS] = {0};
// Increase the count in array if a character
// is found
for (int i = 0; i < n; i++)
count[str[i]]++;
int max_distinct = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
max_distinct++;
return max_distinct;
}
int smallesteSubstr_maxDistictChar(string str){
int n = str.size(); // size of given string
// Find maximum distinct characters in any string
int max_distinct = max_distinct_char(str, n);
int minl = n; // result
// Brute force approach to find all substrings
for (int i=0 ;i<n ;i++){
for (int j=0; j<n; j++){
string subs = str.substr(i,j);
int subs_lenght = subs.size();
int sub_distinct_char = max_distinct_char(subs, subs_lenght);
// We have to check here both conditions together
// 1. substring's distinct characters is equal
// to maximum distinct characters
// 2. substring's length should be minimum
if (subs_lenght < minl && max_distinct == sub_distinct_char){
minl = subs_lenght;
}
}
}
return minl;
}
/* Driver program to test above function */
int main()
{
// Input String
string str = "AABBBCBB";
int len = smallesteSubstr_maxDistictChar(str);
cout << " The length of the smallest substring"
" consisting of maximum distinct "
"characters : " << len;
return 0;
}
Java
/* Java program to find the length of the smallest
substring consisting of maximum distinct characters */
class GFG {
final static int NO_OF_CHARS = 256;
// Find maximum distinct characters in any string
static int max_distinct_char(String str, int n) {
// Initialize all character's count with 0
int count[] = new int[NO_OF_CHARS];
// Increase the count in array if a character
// is found
for (int i = 0; i < n; i++) {
count[str.charAt(i)]++;
}
int max_distinct = 0;
for (int i = 0; i < NO_OF_CHARS; i++) {
if (count[i] != 0) {
max_distinct++;
}
}
return max_distinct;
}
static int smallesteSubstr_maxDistictChar(String str) {
int n = str.length(); // size of given string
// Find maximum distinct characters in any string
int max_distinct = max_distinct_char(str, n);
int minl = n; // result
// Brute force approach to find all substrings
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
String subs = null;
if(i<j)
subs = str.substring(i, j);
else
subs = str.substring(j, i);
int subs_lenght = subs.length();
int sub_distinct_char = max_distinct_char(subs, subs_lenght);
// We have to check here both conditions together
// 1. substring's distinct characters is equal
// to maximum distinct characters
// 2. substring's length should be minimum
if (subs_lenght < minl && max_distinct == sub_distinct_char) {
minl = subs_lenght;
}
}
}
return minl;
}
/* Driver program to test above function */
static public void main(String[] args) {
// Input String
String str = "AABBBCBB";
int len = smallesteSubstr_maxDistictChar(str);
System.out.println(" The length of the smallest substring"
+ " consisting of maximum distinct "
+ "characters : "+len);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to find the length # of the smallest substring consisting # of maximum distinct characters NO_OF_CHARS = 256 # Find maximum distinct characters # in any string def max_distinct_char(str, n): # Initialize all character's # count with 0 count = [0] * NO_OF_CHARS # Increase the count in array # if a character is found for i in range(n): count[ord(str[i])] += 1 max_distinct = 0 for i in range(NO_OF_CHARS): if (count[i] != 0): max_distinct += 1 return max_distinct def smallesteSubstr_maxDistictChar(str): n = len(str) # size of given string # Find maximum distinct characters # in any string max_distinct = max_distinct_char(str, n) minl = n # result # Brute force approach to # find all substrings for i in range(n): for j in range(n): subs = str[i:j] subs_lenght = len(subs) sub_distinct_char = max_distinct_char(subs, subs_lenght) # We have to check here both conditions together # 1. substring's distinct characters is equal # to maximum distinct characters # 2. substring's length should be minimum if (subs_lenght < minl and max_distinct == sub_distinct_char): minl = subs_lenght return minl # Driver Code if __name__ == "__main__": # Input String str = "AABBBCBB" l = smallesteSubstr_maxDistictChar(str); print( "The length of the smallest substring", "consisting of maximum distinct", "characters :", l) # This code is contributed by ChitraNayal
C#
/* C# program to find the length of the smallest
substring consisting of maximum distinct characters */
using System;
class GFG
{
static int NO_OF_CHARS = 256;
// Find maximum distinct characters in any string
static int max_distinct_char(String str, int n)
{
// Initialize all character's count with 0
int []count = new int[NO_OF_CHARS];
// Increase the count in array if a character
// is found
for (int i = 0; i < n; i++)
{
count[str[i]]++;
}
int max_distinct = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if (count[i] != 0)
{
max_distinct++;
}
}
return max_distinct;
}
static int smallesteSubstr_maxDistictChar(String str)
{
int n = str.Length; // size of given string
// Find maximum distinct characters in any string
int max_distinct = max_distinct_char(str, n);
int minl = n; // result
// Brute force approach to find all substrings
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
String subs = null;
if(i < j)
subs = str.Substring(i, str.Length-j);
else
subs = str.Substring(j, str.Length-i);
int subs_lenght = subs.Length;
int sub_distinct_char = max_distinct_char(subs, subs_lenght);
// We have to check here both conditions together
// 1. substring's distinct characters is equal
// to maximum distinct characters
// 2. substring's length should be minimum
if (subs_lenght < minl && max_distinct == sub_distinct_char)
{
minl = subs_lenght;
}
}
}
return minl;
}
/* Driver program to test above function */
static public void Main(String[] args)
{
// Input String
String str = "AABBBCBB";
int len = smallesteSubstr_maxDistictChar(str);
Console.WriteLine(" The length of the smallest substring"
+ " consisting of maximum distinct "
+ "characters : "+len);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
/* PHP program to find the length of the smallest
substring consisting of maximum distinct characters */
$NO_OF_CHARS=256;
// Find maximum distinct characters in any string
function max_distinct_char($str, $n)
{
global $NO_OF_CHARS;
// Initialize all character's count with 0
$count = array_fill(0, $NO_OF_CHARS, 0);
// Increase the count in array if a character
// is found
for ($i = 0; $i < $n; $i++)
$count[ord($str[$i])]++;
$max_distinct = 0;
for ($i = 0; $i < $NO_OF_CHARS; $i++)
if ($count[$i] != 0)
$max_distinct++;
return $max_distinct;
}
function smallesteSubstr_maxDistictChar($str)
{
$n = strlen($str); // size of given string
// Find maximum distinct characters in any string
$max_distinct = max_distinct_char($str, $n);
$minl = $n; // result
// Brute force approach to find all substrings
for ($i = 0 ; $i < $n ; $i++)
{
for ($j = 0; $j < $n; $j++)
{
$subs = substr($str, $i, $j);
$subs_lenght = strlen($subs);
$sub_distinct_char = max_distinct_char($subs, $subs_lenght);
// We have to check here both conditions together
// 1. substring's distinct characters is equal
// to maximum distinct characters
// 2. substring's length should be minimum
if ($subs_lenght < $minl &&
$max_distinct == $sub_distinct_char)
{
$minl = $subs_lenght;
}
}
}
return $minl;
}
/* Driver code */
// Input String
$str = "AABBBCBB";
$len = smallesteSubstr_maxDistictChar($str);
echo " The length of the smallest substring"
." consisting of maximum distinct characters : ".$len;
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the length
// of the smallest substring consisting
// of maximum distinct characters
let NO_OF_CHARS = 256;
// Find maximum distinct characters
// in any string
function max_distinct_char(str, n)
{
// Initialize all character's
// count with 0
let count = new Array(NO_OF_CHARS);
for(let i = 0; i < count.length; i++)
{
count[i] = 0;
}
// Increase the count in array if a
// character is found
for(let i = 0; i < n; i++)
{
count[str[i].charCodeAt(0)]++;
}
let max_distinct = 0;
for(let i = 0; i < NO_OF_CHARS; i++)
{
if (count[i] != 0)
{
max_distinct++;
}
}
return max_distinct;
}
function smallesteSubstr_maxDistictChar(str)
{
// Size of given string
let n = str.length;
// Find maximum distinct characters
// in any string
let max_distinct = max_distinct_char(str, n);
// Result
let minl = n;
// Brute force approach to find all
// substrings
for(let i = 0; i < n; i++)
{
for(let j = 0; j < n; j++)
{
let subs = null;
if (i < j)
subs = str.substring(i, j);
else
subs = str.substring(j, i);
let subs_lenght = subs.length;
let sub_distinct_char = max_distinct_char(
subs, subs_lenght);
// We have to check here both conditions together
// 1. substring's distinct characters is equal
// to maximum distinct characters
// 2. substring's length should be minimum
if (subs_lenght < minl &&
max_distinct == sub_distinct_char)
{
minl = subs_lenght;
}
}
}
return minl;
}
// Driver Code
let str = "AABBBCBB";
let len = smallesteSubstr_maxDistictChar(str);
document.write("The length of the smallest substring" +
" consisting of maximum distinct " +
"characters : " + len);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
The length of the smallest substring consisting of maximum distinct characters : 5
Complejidad de Tiempo: O(n 3 )
Espacio Auxiliar: O(n)
Método 2 (eficiente)
- Cuente todos los caracteres distintos en una string dada.
- Mantener una ventana de caracteres. Cada vez que la ventana contiene todos los caracteres de la string dada, la encogemos desde el lado izquierdo para eliminar los caracteres adicionales y luego comparamos su longitud con la ventana más pequeña encontrada hasta el momento.
Implementación:
C++
/* C++ program to find the length of the smallest
substring consisting of maximum distinct characters */
#include <bits/stdc++.h>
using namespace std;
// A function which accepts a string and returns length of
// the smallest substring consisting of maximum distinct
// characters
int smallesteSubstr_maxDistictChar(string str)
{
// to get the number of unique characters
unordered_set<char> st;
// traverse the string once and store the characters
for (int i = 0; i < str.length(); i++)
st.insert(str[i]);
// number of unique characters
int unique = st.size();
unordered_map<char, int> mp;
// to store the result
int res = INT_MAX;
int j = 0; // starting index of window
for (int i = 0; i < str.length(); i++) {
// add the current chararcter in window
mp[str[i]]++;
// while number of distinct elements in the map is
// equal to unique characters and starting element
// of the window has frequency more than one we keep
// reducing its frequency and increasing the
// starting point of the window
while (mp.size() == unique && mp[str[j]] > 1) {
mp[str[j]]--;
j++;
}
// if size of map is equal to unique elements update
// the result
if (mp.size() == unique)
res = min(i - j + 1, res);
}
return res;
}
/* Driver program to test above function */
int main()
{
// Input String
string str = "AABBBCBB";
int len = smallesteSubstr_maxDistictChar(str);
cout << " The length of the smallest substring"
" consisting of maximum distinct "
"characters : "
<< len;
return 0;
}
// This code was contributed by Abhijeet Kumar(abhijeet19403)
Java
/* Java program to find the length of the smallest
substring consisting of maximum distinct characters */
import java.util.*;
class GFG {
static final int MAX_CHARS = 256;
// Find maximum distinct characters in any string
static int max_distinct_char(String str, int n)
{
// Initialize all character's count with 0
int count[] = new int[MAX_CHARS];
int max_distinct = 0;
// Increase the count of max_distinct if a character
// is found to have a frequency of 1
for (int i = 0; i < n; i++) {
count[str.charAt(i)]++;
if (count[str.charAt(i)] == 1)
max_distinct++;
}
return max_distinct;
}
// A function which accepts a string and returns length
// of the smallest substring consisting of maximum distinct
// characters
static int smallestSubstr_maxDistictChar(String str)
{
int n = str.length();
// number of unique characters
int unique = max_distinct_char(str, n);
// to store the result
int res = Integer.MAX_VALUE;
Map<Character, Integer> mp
= new HashMap<Character, Integer>();
int j = 0; // starting index of window
for (int i = 0; i < str.length(); i++) {
// add the current chararcter in window
char c = str.charAt(i);
if (mp.containsKey(c))
mp.put(c, mp.get(c) + 1);
else
mp.put(c, 1);
// while no. of distinct elements in the map is
// equal to unique characters and starting
// element of the window has frequency more than
// one we keep reducing its frequency and
// increasing the starting point of the window
while (mp.size() == unique
&& mp.get(str.charAt(j)) > 1) {
mp.put(str.charAt(j),
(mp.get(str.charAt(j)) - 1));
j++;
}
// if size of map is equal to unique elements
// update the result
if (mp.size() == unique)
res = Math.min(i - j + 1, res);
}
return res;
}
/* Driver program to test above function */
static public void main(String[] args)
{
// Input String
String str = "AABBBCBB";
int len = smallestSubstr_maxDistictChar(str);
System.out.println(
" The length of the smallest substring"
+ " consisting of maximum distinct "
+ "characters : " + len);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
/* C# program to find the length of the smallest
substring consisting of maximum distinct characters */
using System;
using System.Collections.Generic;
class GFG
{
static int MAX_CHARS = 256;
// Find maximum distinct characters in any string
static int max_distinct_char(String str, int n)
{
// Initialize all character's count with 0
int[] count = new int[MAX_CHARS];
int max_distinct = 0;
// Increase the count of max_distinct if a character
// is found to have a frequency of 1
for (int i = 0; i < n; i++) {
count[str[i]]++;
if (count[str[i]] == 1)
max_distinct++;
}
return max_distinct;
}
static int smallestSubstr_maxDistictChar(String str)
{
int n = str.Length;
// number of unique characters
int unique = max_distinct_char(str, n);
// to store the result
int res = int.MaxValue;
Dictionary<char, int> mp = new Dictionary<char, int>();
int j = 0; // starting index of window
for (int i = 0; i < n; i++) {
// add the current chararcter in window
if (mp.ContainsKey(str[i]))
mp[str[i]]++;
else
mp.Add(str[i], 1);
// while no. of distinct elements in the map is
// equal to unique characters and starting
// element of the window has frequency more than
// one we keep reducing its frequency and
// increasing the starting point of the window
while (mp.Count == unique && mp[str[j]] > 1)
{
mp[str[j]]--;
j++;
}
// if size of map is equal to unique elements
// update the result
if (mp.Count == unique)
res = Math.Min(i - j + 1, res);
}
return res;
}
/* Driver program to test above function */
static public void Main(String[] args)
{
// Input String
String str = "AABBBCBB";
int len = smallestSubstr_maxDistictChar(str);
Console.WriteLine(" The length of the smallest substring"
+ " consisting of maximum distinct "
+ "characters : "+len);
}
}
// This code contributed by Abhijeet Kumar(abhijeet19403)
Producción
The length of the smallest substring consisting of maximum distinct characters : 5
Complejidad de tiempo: O(n), mientras hacemos operaciones lineales en strings.
Espacio Auxiliar: O(n), Como espacio extra constante se utiliza. El tamaño del conjunto y el mapa solo puede alcanzar un tamaño máximo de 256, que es una constante, por lo que el espacio adicional utilizado también es constante.
Consulte la Ventana más pequeña que contiene todos los caracteres de la string para obtener más detalles.
Preguntado en: DailyHunt
Este artículo es una contribución de Harshit Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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