Dada una string str , la tarea es encontrar la longitud mínima de las substrings de modo que todas las substrings de esa longitud de str contengan al menos un carácter común . Si no se puede obtener tal longitud, imprima -1 .
Ejemplo:
Entrada: str = “saad”
Salida: 2
Explicación:
Todas las substrings de longitud dos de una string dada son { “sa”, “aa”, “ad” }.
Dado que ‘a’ es común entre todas las substrings, la longitud mínima posible de las substrings que tienen al menos un carácter común es 2 .Entrada: str = “geeksforgeeks”
Salida: 7
Explicación:
Todas las substrings posibles de longitud 7 son las siguientes:
- g e eksfo
- e eksfor
- e ksforg
- ksforg e
- forjar e
- forjar e k
- orge eks _
mi 7
Enfoque: este problema se puede resolver fácilmente utilizando la técnica de búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice low como 1 y high como una longitud de la string str .
- Encuentra medio entre bajo y alto.
- Si hay un carácter común en todas las substrings de una string dada, entonces actualice hasta mediados de -1.
- Si no es el caso, actualice bajo como un medio + 1 .
- Repita los pasos anteriores para los 26 caracteres posibles del alfabeto .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check and return if
// substrings of length mid has a
// common character a
bool check(string& str, int mid, char a)
{
// Length of the string
int n = str.size();
// Initialise the first
// occurrence of character a
int previous = -1, i;
for (i = 0; i < n; ++i) {
if (str[i] == a) {
// Check that distance b/w
// the current and previous
// occurrence of character a
// is less than or equal to mid
if (i - previous > mid) {
return false;
}
previous = i;
}
}
// If distance exceeds mid
if (i - previous > mid)
return false;
else
return true;
}
// Function to check for all the
// alphabets, if substrings of
// length mid have a character common
bool possible(string& str, int mid)
{
// Check for all 26 alphabets
for (int i = 0; i < 26; ++i) {
// Check that char i + a is
// common in all the substrings
// of length mid
if (check(str, mid, i + 'a'))
return true;
}
// If no characters is common
return false;
}
// Function to calculate and return
// the minm length of substrings
int findMinLength(string& str)
{
// Initialise low and high
int low = 1, high = str.length();
// Perform binary search
while (low <= high) {
// Update mid
int mid = (low + high) / 2;
// Check if one common character is
// present in the length of the mid
if (possible(str, mid))
high = mid - 1;
else
low = mid + 1;
}
// Returns the minimum length
// that contain one
// common character
return high + 1;
}
// Function to check if all
// characters are distinct
bool ifAllDistinct(string str)
{
set<char> s;
for (char c : str) {
s.insert(c);
}
return s.size() == str.size();
}
// Driver Code
int main()
{
string str = "geeksforgeeks";
if (ifAllDistinct(str))
cout << -1 << endl;
else
cout << findMinLength(str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check and return if
// subStrings of length mid has a
// common character a
static boolean check(char[] str, int mid,
char a)
{
// Length of the String
int n = str.length;
// Initialise the first
// occurrence of character a
int previous = -1, i;
for(i = 0; i < n; ++i)
{
if (str[i] == a)
{
// Check that distance b/w
// the current and previous
// occurrence of character a
// is less than or equal to mid
if (i - previous > mid)
{
return false;
}
previous = i;
}
}
// If distance exceeds mid
if (i - previous > mid)
return false;
else
return true;
}
// Function to check for all the
// alphabets, if subStrings of
// length mid have a character common
static boolean possible(char[] str, int mid)
{
// Check for all 26 alphabets
for(int i = 0; i < 26; ++i)
{
// Check that char i + a is
// common in all the subStrings
// of length mid
if (check(str, mid, (char)(i + 'a')))
return true;
}
// If no characters is common
return false;
}
// Function to calculate and return
// the minm length of subStrings
static int findMinLength(char[] str)
{
// Initialise low and high
int low = 1, high = str.length;
// Perform binary search
while (low <= high)
{
// Update mid
int mid = (low + high) / 2;
// Check if one common character is
// present in the length of the mid
if (possible(str, mid))
high = mid - 1;
else
low = mid + 1;
}
// Returns the minimum length
// that contain one
// common character
return high + 1;
}
// Function to check if all
// characters are distinct
static boolean ifAllDistinct(String str)
{
HashSet<Character> s = new HashSet<Character>();
for(char c : str.toCharArray())
{
s.add(c);
}
return s.size() == str.length();
}
// Driver Code
public static void main(String[] args)
{
String str = "geeksforgeeks";
if (ifAllDistinct(str))
System.out.print(-1 + "\n");
else
System.out.print(findMinLength(
str.toCharArray()));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to check and return if
# substrings of length mid has a
# common character a
def check(st, mid, a):
# Length of the string
n = len(st)
# Initialise the first
# occurrence of character a
previous = -1
for i in range(n):
if (st[i] == chr(a)):
# Check that distance b/w
# the current and previous
# occurrence of character a
# is less than or equal to mid
if (i - previous > mid):
return False
previous = i
# If distance exceeds mid
if (i - previous > mid):
return False
else:
return True
# Function to check for all the
# alphabets, if substrings of
# length mid have a character common
def possible(st, mid):
# Check for all 26 alphabets
for i in range(26):
# Check that char i + a is
# common in all the substrings
# of length mid
if (check(st, mid, i + ord('a'))):
return True
# If no characters is common
return False
# Function to calculate and return
# the minm length of substrings
def findMinLength(st):
# Initialise low and high
low = 1
high = len(st)
# Perform binary search
while (low <= high):
# Update mid
mid = (low + high) // 2
# Check if one common character is
# present in the length of the mid
if (possible(st, mid)):
high = mid - 1
else:
low = mid + 1
# Returns the minimum length
# that contain one
# common character
return high + 1
# Function to check if all
# characters are distinct
def ifAllDistinct( st):
s = []
for c in st:
s.append(c)
return len(set(s)) == len(st)
# Driver Code
if __name__ == "__main__":
st = "geeksforgeeks"
if (ifAllDistinct(st)):
print("-1")
else:
print(findMinLength(st))
# This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check and return if
// subStrings of length mid has a
// common character a
static bool check(char[] str, int mid,
char a)
{
// Length of the String
int n = str.Length;
// Initialise the first
// occurrence of character a
int previous = -1, i;
for(i = 0; i < n; ++i)
{
if (str[i] == a)
{
// Check that distance b/w
// the current and previous
// occurrence of character a
// is less than or equal to mid
if (i - previous > mid)
{
return false;
}
previous = i;
}
}
// If distance exceeds mid
if (i - previous > mid)
return false;
else
return true;
}
// Function to check for all the
// alphabets, if subStrings of
// length mid have a character common
static bool possible(char[] str, int mid)
{
// Check for all 26 alphabets
for(int i = 0; i < 26; ++i)
{
// Check that char i + a is
// common in all the subStrings
// of length mid
if (check(str, mid, (char)(i + 'a')))
return true;
}
// If no characters is common
return false;
}
// Function to calculate and return
// the minm length of subStrings
static int findMinLength(char[] str)
{
// Initialise low and high
int low = 1, high = str.Length;
// Perform binary search
while (low <= high)
{
// Update mid
int mid = (low + high) / 2;
// Check if one common character is
// present in the length of the mid
if (possible(str, mid))
high = mid - 1;
else
low = mid + 1;
}
// Returns the minimum length
// that contain one
// common character
return high + 1;
}
// Function to check if all
// characters are distinct
static bool ifAllDistinct(String str)
{
HashSet<char> s = new HashSet<char>();
foreach(char c in str.ToCharArray())
{
s.Add(c);
}
return s.Count == str.Length;
}
// Driver Code
public static void Main(String[] args)
{
String str = "geeksforgeeks";
if (ifAllDistinct(str))
Console.Write(-1 + "\n");
else
Console.Write(findMinLength(
str.ToCharArray()));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check and return if
// subStrings of length mid has a
// common character a
function check(str, mid, a)
{
// Length of the String
var n = str.length;
// Initialise the first
// occurrence of character a
var previous = -1,
i;
for(i = 0; i < n; ++i)
{
if (str[i] === a)
{
// Check that distance b/w
// the current and previous
// occurrence of character a
// is less than or equal to mid
if (i - previous > mid)
{
return false;
}
previous = i;
}
}
// If distance exceeds mid
if (i - previous > mid)
return false;
else
return true;
}
// Function to check for all the
// alphabets, if subStrings of
// length mid have a character common
function possible(str, mid)
{
// Check for all 26 alphabets
for(var i = 0; i < 26; ++i)
{
// Check that char i + a is
// common in all the subStrings
// of length mid
if (check(str, mid,
String.fromCharCode(
i + "a".charCodeAt(0))))
return true;
}
// If no characters is common
return false;
}
// Function to calculate and return
// the minm length of subStrings
function findMinLength(str)
{
// Initialise low and high
var low = 1,
high = str.length;
// Perform binary search
while (low <= high)
{
// Update mid
var mid = parseInt((low + high) / 2);
// Check if one common character is
// present in the length of the mid
if (possible(str, mid))
high = mid - 1;
else
low = mid + 1;
}
// Returns the minimum length
// that contain one
// common character
return high + 1;
}
// Function to check if all
// characters are distinct
function ifAllDistinct(str)
{
var s = new Array();
var temp = str.split("");
for(const c of temp)
{
s.push(c);
}
var set = new Set(s);
return set.size === str.length;
}
// Driver Code
var str = "geeksforgeeks";
if (ifAllDistinct(str))
document.write(-1 + "<br>");
else
document.write(
findMinLength(str.split("")));
// This code is contributed by rdtank
</script>
Producción:
7
Complejidad de tiempo: O(26 * N * log(N))
Espacio auxiliar: O(1)