Dada una string de letras minúsculas S un carácter c . La tarea es encontrar el mínimo K tal que cada substring de longitud K contenga el carácter c dado . Si no existe tal K posible, devuelve -1 .
Ejemplos:
Entrada: S = “abdegb”, ch = ‘b’
Salida: 4
Explicación:
Considere el valor de K como 4. Ahora, cada substring de tamaño K(= 4) son {“abde”, “bdeg”, “degb” } tiene el carácter ch(= b’).Entrada: S = “abfge”, ch = ‘m’
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar para todos los tamaños posibles de substrings en el rango [1, N] y verificar qué valor mínimo de K satisface los criterios dados. Si no existe tal valor de K , imprima “-1” .
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la observación de que el valor mínimo de K es igual a la diferencia máxima entre las ocurrencias consecutivas del carácter ch dado, ya que para cada substring de tamaño K debe tener al menos 1 carácter como cap . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos maxDifference como -1 que almacene el valor resultante de K .
- Inicializa una variable, digamos anterior como 0 que almacena la aparición anterior del carácter ch en la string S .
- Recorra la string dada S usando la variable i y si el carácter actual es ch , actualice el valor de maxDifference al máximo de maxDifference y (i – anterior) y el valor anterior a i .
- Después de completar los pasos anteriores, imprima el valor de maxDifference como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum value
// of K such that char c occurs in all
// K sized substrings of string S
int findK(string s, char c)
{
// Store the string length
int n = s.size();
// Store difference of lengths
// of segments of every two
// consecutive occurrences of c
int diff;
// Stores the maximum difference
int max = 0;
// Store the previous occurrence
// of char c
int prev = 0;
for (int i = 0; i < n; i++) {
// Check if the current character
// is c or not
if (s[i] == c) {
// Stores the difference of
// consecutive occurrences of c
diff = i - prev;
// Update previous occurrence
// of c with current occurrence
prev = i;
// Comparing diff with max
if (diff > max) {
max = diff;
}
}
}
// If string doesn't contain c
if (max == 0)
return -1;
// Return max
return max;
}
// Driver Code
int main() {
string S = "abdegb";
char ch = 'b';
cout<<(findK(S, ch));
return 0;
}
// This code is contributed by 29AjayKumar
Java
// Java program for the above approach
class GFG {
// Function to find the minimum value
// of K such that char c occurs in all
// K sized substrings of string S
public static int findK(String s, char c)
{
// Store the string length
int n = s.length();
// Store difference of lengths
// of segments of every two
// consecutive occurrences of c
int diff;
// Stores the maximum difference
int max = 0;
// Store the previous occurrence
// of char c
int prev = 0;
for (int i = 0; i < n; i++) {
// Check if the current character
// is c or not
if (s.charAt(i) == c) {
// Stores the difference of
// consecutive occurrences of c
diff = i - prev;
// Update previous occurrence
// of c with current occurrence
prev = i;
// Comparing diff with max
if (diff > max) {
max = diff;
}
}
}
// If string doesn't contain c
if (max == 0)
return -1;
// Return max
return max;
}
// Driver Code
public static void main(String args[]) {
String S = "abdegb";
char ch = 'b';
System.out.println(findK(S, ch));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python program for the above approach # Function to find the minimum value # of K such that char c occurs in all # K sized substrings of string S def findK(s, c): # Store the string length n = len(s) # Store difference of lengths # of segments of every two # consecutive occurrences of c diff = 0 # Stores the maximum difference max = 0 # Store the previous occurrence # of char c prev = 0 for i in range(0, n): # Check if the current character # is c or not if (s[i] == c): # Stores the difference of # consecutive occurrences of c diff = i - prev # Update previous occurrence # of c with current occurrence prev = i # Comparing diff with max if (diff > max): max = diff # If string doesn't contain c if (max == 0): return -1 # Return max return max # Driver Code if __name__ == "__main__": S = "abdegb" ch = 'b' print(findK(S, ch)) # This code is contributed by rakeshsahni
C#
using System.Collections.Generic;
using System;
class GFG
{
// Function to find the minimum value
// of K such that char c occurs in all
// K sized substrings of string S
public static int findK(string s, char c)
{
// Store the string length
int n = s.Length;
// Store difference of lengths
// of segments of every two
// consecutive occurrences of c
int diff;
// Stores the maximum difference
int max = 0;
// Store the previous occurrence
// of char c
int prev = 0;
for (int i = 0; i < n; i++) {
// Check if the current character
// is c or not
if (s[i] == c) {
// Stores the difference of
// consecutive occurrences of c
diff = i - prev;
// Update previous occurrence
// of c with current occurrence
prev = i;
// Comparing diff with max
if (diff > max) {
max = diff;
}
}
}
// If string doesn't contain c
if (max == 0)
return -1;
// Return max
return max;
}
// Driver Code
public static void Main()
{
string S = "abdegb";
char ch = 'b';
Console.WriteLine(findK(S, ch));
}
}
// This code is contributed by amreshkumar3.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum value
// of K such that char c occurs in all
// K sized substrings of string S
function findK(s, c)
{
// Store the string length
let n = s.length;
// Store difference of lengths
// of segments of every two
// consecutive occurrences of c
let diff;
// Stores the maximum difference
let max = 0;
// Store the previous occurrence
// of char c
let prev = 0;
for (let i = 0; i < n; i++) {
// Check if the current character
// is c or not
if (s[i] == c) {
// Stores the difference of
// consecutive occurrences of c
diff = i - prev;
// Update previous occurrence
// of c with current occurrence
prev = i;
// Comparing diff with max
if (diff > max) {
max = diff;
}
}
}
// If string doesn't contain c
if (max == 0) return -1;
// Return max
return max;
}
// Driver Code
let S = "abdegb";
let ch = "b";
document.write(findK(S, ch));
// This code is contributed by saurabh_jaiswal.
</script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA