Dada una string S que contiene letras latinas en minúsculas. Un carácter c se llama K-asombroso si cada substring de S con una longitud de al menos K contiene este carácter c. Encuentre el K mínimo posible tal que exista al menos un carácter K-asombroso.
Ejemplos:
Entrada: S = “abcde”
Salida: 3
Explicación: cada substring de longitud de al menos 3 contiene el carácter ‘c’, es decir,
{“abc”, “bcd”, “cde”, “abcd”, “bcde”, “abcde”}
Entrada: S = “aaaa”
Salida: 1
Prerrequisitos: solución ingenua de búsqueda binaria : un enfoque simple es iterar sobre todas las longitudes posibles de substrings, es decir, de 1 a N (tamaño de la string) y para cada substring de longitud actual, compruebe si aparece algún carácter en todas esas substrings. Solución eficiente: la idea clave es realizar una búsqueda binaria sobre la respuesta K , ya que si algún carácter c aparece en todas las substrings de longitud X , siempre aparecerá en todas las substrings de longitud (X + 1)
. Por lo tanto, podemos verificar la longitud actual e intentar minimizarla usando el algoritmo divide y vencerás. Para verificar si algún carácter aparece en todas las substrings de longitud X, itere sobre todos los caracteres de ‘a’ a ‘z’ y dentro de otro ciclo almacene iterativamente la última aparición del último carácter.
Deje que la posición actual sea j, por lo que la última substring de longitud X será de (j – X) a X. Compruebe si la posición de la última aparición del carácter K-asombroso actual es mayor que (j – X) o no. Si es mayor, entonces esa substring es una string válida.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP Program to find minimum K such that
// every substring of length atleast K
// contains some character c
#include <bits/stdc++.h>
using namespace std;
// This function checks if there exists some
// character which appears in all K length
// substrings
int check(string s, int K)
{
// Iterate over all possible characters
for (int ch = 0; ch < 26; ch++) {
char c = 'a' + ch;
// stores the last occurrence
int last = -1;
// set answer as true;
bool found = true;
for (int i = 0; i < K; i++)
if (s[i] == c)
last = i;
// No occurrence found of current
// character in first substring
// of length K
if (last == -1)
continue;
// Check for every last substring
// of length K where last occurr-
// ence exists in substring
for (int i = K; i < s.size(); i++) {
if (s[i] == c)
last = i;
// If last occ is not
// present in substring
if (last <= (i - K)) {
found = false;
break;
}
}
// current character is K amazing
if (found)
return 1;
}
return 0;
}
// This function performs binary search over the
// answer to minimise it
int binarySearch(string s)
{
int low = 1, high = (int)s.size();
int ans;
while (low <= high) {
int mid = (high + low) >> 1;
// Check if answer is found try
// to minimise it
if (check(s, mid)) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code to test above functions
int32_t main()
{
string s = "abcde";
cout << binarySearch(s) << endl;
s = "aaaa";
cout << binarySearch(s) << endl;
return 0;
}
Java
// Java Program to find minimum K such that
// every substring of length atleast K
// contains some character c
class GFG
{
// This function checks if there exists some
// character which appears in all K length
// substrings
static int check(String s, int K)
{
// Iterate over all possible characters
for (int ch = 0; ch < 26; ch++) {
char c = (char)( 'a' + ch);
// stores the last occurrence
int last = -1;
// set answer as true;
boolean found = true;
for (int i = 0; i < K; i++)
if (s.charAt(i) == c)
last = i;
// No occurrence found of current
// character in first substring
// of length K
if (last == -1)
continue;
// Check for every last substring
// of length K where last occurr-
// ence exists in substring
for (int i = K; i < s.length(); i++) {
if (s.charAt(i) == c)
last = i;
// If last occ is not
// present in substring
if (last <= (i - K)) {
found = false;
break;
}
}
// current character is K amazing
if (found)
return 1;
}
return 0;
}
// This function performs binary search over the
// answer to minimise it
static int binarySearch(String s)
{
int low = 1, high = s.length();
int ans=0;
while (low <= high) {
int mid = (high + low) >> 1;
// Check if answer is found try
// to minimise it
if (check(s, mid)==1) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code to test above functions
public static void main(String args[])
{
String s = "abcde";
System.out.println(binarySearch(s));
s = "aaaa";
System.out.println(binarySearch(s));
}
}
// This article is contributed
// by ihritik
Python3
# Python3 Program to find minimum K such # that every substring of length atleast # K contains some character c # This function checks if there exists # some character which appears in all # K length substrings def check(s, K): # Iterate over all possible characters for ch in range(0, 26): c = chr(97 + ch) # Ascii value of 'a' => 97 # stores the last occurrence last = -1 # set answer as true found = True for i in range(0, K): if s[i] == c: last = i # No occurrence found of current character # in first substring of length K if last == -1: continue # Check for every last substring # of length K where last occurr- # ence exists in substring for i in range(K, len(s)): if s[i] == c: last = i # If last occ is not # present in substring if last <= (i - K): found = False break # current character is K amazing if found: return 1 return 0 # This function performs binary search # over the answer to minimise it def binarySearch(s): low, high, ans = 1, len(s), None while low <= high: mid = (high + low) >> 1 # Check if answer is found # try to minimise it if check(s, mid): ans, high = mid, mid - 1 else: low = mid + 1 return ans # Driver Code if __name__ == "__main__": s = "abcde" print(binarySearch(s)) s = "aaaa" print(binarySearch(s)) # This code is contributed by Rituraj Jain
C#
// C# Program to find minimum K such that
// every substring of length atleast K
// contains some character c
using System;
class GFG
{
// This function checks if there exists some
// character which appears in all K length
// substrings
static int check(String s, int K)
{
// Iterate over all possible characters
for (int ch = 0; ch < 26; ch++) {
char c = (char)( 'a' + ch);
// stores the last occurrence
int last = -1;
// set answer as true;
bool found = true;
for (int i = 0; i < K; i++)
if (s[i] == c)
last = i;
// No occurrence found of current
// character in first substring
// of length K
if (last == -1)
continue;
// Check for every last substring
// of length K where last occurr-
// ence exists in substring
for (int i = K; i < s.Length; i++) {
if (s[i] == c)
last = i;
// If last occ is not
// present in substring
if (last <= (i - K)) {
found = false;
break;
}
}
// current character is K amazing
if (found)
return 1;
}
return 0;
}
// This function performs binary search over the
// answer to minimise it
static int binarySearch(String s)
{
int low = 1, high = s.Length;
int ans=0;
while (low <= high) {
int mid = (high + low) >> 1;
// Check if answer is found try
// to minimise it
if (check(s, mid)==1) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code to test above functions
public static void Main()
{
String s = "abcde";
Console.WriteLine(binarySearch(s));
s = "aaaa";
Console.WriteLine(binarySearch(s));
}
}
// This article is contributed
// by ihritik
PHP
<?php
// Php Program to find minimum K such that
// every substring of length atleast K
// contains some character c
// This function checks if there exists some
// character which appears in all K length
// substrings
function check($s, $K)
{
// Iterate over all possible characters
for ($ch = 0; $ch < 26; $ch++)
{
$c = chr(ord('a') + $ch) ;
// stores the last occurrence
$last = -1;
// set answer as true;
$found = true;
for ($i = 0; $i < $K; $i++)
if ($s[$i] == $c)
$last = $i;
// No occurrence found of current
// character in first substring
// of length K
if ($last == -1)
continue;
// Check for every last substring
// of length K where last occurr-
// ence exists in substring
for ($i = $K; $i < strlen($s); $i++)
{
if ($s[$i] == $c)
$last = $i;
// If last occ is not
// present in substring
if ($last <= ($i - $K))
{
$found = false;
break;
}
}
// current character is K amazing
if ($found)
return 1;
}
return 0;
}
// This function performs binary search
// over the answer to minimise it
function binarySearch($s)
{
$low = 1 ;
$high = strlen($s) ;
while ($low <= $high)
{
$mid = ($high + $low) >> 1;
// Check if answer is found try
// to minimise it
if (check($s, $mid))
{
$ans = $mid;
$high = $mid - 1;
}
else
$low = $mid + 1;
}
return $ans;
}
// Driver Code
$s = "abcde";
echo binarySearch($s) . "\n";
$s = "aaaa";
echo binarySearch($s) . "\n";
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript Program to find minimum K such that
// every substring of length atleast K
// contains some character c
// This function checks if there exists some
// character which appears in all K length
// substrings
function check(s, K)
{
// Iterate over all possible characters
for (var ch = 0; ch < 26; ch++) {
var c = String.fromCharCode('a'.charCodeAt(0) + ch);
// stores the last occurrence
var last = -1;
// set answer as true;
var found = true;
for (var i = 0; i < K; i++)
if (s[i] == c)
last = i;
// No occurrence found of current
// character in first substring
// of length K
if (last == -1)
continue;
// Check for every last substring
// of length K where last occurr-
// ence exists in substring
for (var i = K; i < s.length; i++) {
if (s[i] == c)
last = i;
// If last occ is not
// present in substring
if (last <= (i - K)) {
found = false;
break;
}
}
// current character is K amazing
if (found)
return 1;
}
return 0;
}
// This function performs binary search over the
// answer to minimise it
function binarySearch(s)
{
var low = 1, high = s.length;
var ans;
while (low <= high) {
var mid = (high + low) >> 1;
// Check if answer is found try
// to minimise it
if (check(s, mid)) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code to test above functions
var s = "abcde";
document.write( binarySearch(s) + "<br>");
s = "aaaa";
document.write( binarySearch(s) );
</script>
Producción:
3 1
Complejidad de tiempo: O (N * logN * 26), donde N es el tamaño de la string dada.
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA