Dada una string S y su longitud N (siempre que N > 0 ). La tarea es encontrar la distancia mínima entre los mismos caracteres repetidos, si no hay caracteres repetidos presentes en la string S , devuelve -1 .
Ejemplos:
Entrada: S = «geeksforgeeks», N = 13
Salida: 0
Explicación :
los caracteres repetidos en la string S = «geeksforgeeks» con distancia mínima es ‘e’.
La diferencia mínima de sus índices es 0 (es decir, el carácter ‘e’ está presente en el índice 1 y 2).Entrada: S = “abdfhbih”, N = 8
Salida: 2
Explicación :
Los caracteres repetidos en la string S = “abdfhbih” con distancia mínima es ‘h’.
La diferencia mínima de sus índices es 2 (es decir, el carácter ‘h’ está presente en el índice 4 y 7).
Enfoque ingenuo: este problema se puede resolver usando dos bucles anidados, uno considerando un elemento en cada índice ‘i’ en la string S , el siguiente bucle encontrará el carácter coincidente igual a i th en S.
Primero, almacene cada diferencia entre caracteres repetidos en una variable y verifique si esta distancia actual es menor que el valor anterior almacenado en la misma variable. Al final, devuelve la variable que almacena el valor mínimo . Hay un caso de esquina, es decir, cuando no hay caracteres repetidos, devuelve -1 . Siga los pasos a continuación para resolver este problema:
- Inicialice una variable minDis como N para almacenar las distancias mínimas de caracteres repetidos.
- Iterar en el rango [0, N-1] usando la variable i:
- Iterar en el rango [i + 1, N-1] usando la variable j :
- Si S[i] es igual a S[j] y la distancia entre ellos es menor que minDis, actualice minDis y luego rompa el ciclo
- Iterar en el rango [i + 1, N-1] usando la variable j :
- Si el valor de minDis no se actualiza, eso significa que no hay caracteres repetidos, devuelva -1; de lo contrario, devuelva minDis – 1.
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;
// This function is used to find
// minimum distance between same
// repeating characters
int shortestDistance(string S, int N)
{
// Store minimum distance between same
// repeating characters
int minDis = S.length();
// For loop to consider each element
// of string
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// Comparison of string characters and
// updating the minDis value
if (S[i] == S[j] and (j - i) < minDis)
{
minDis = j - i;
// As this value would be least
// therefore break
break;
}
}
}
// If minDis value is not updated that means
// no repeating characters
if (minDis == S.length())
return -1;
else
// Minimum distance is minDis - 1
return minDis - 1;
}
// Driver Code
int main()
{
// Given Input
string S = "geeksforgeeks";
int N = 13;
// Function Call
cout << (shortestDistance(S, N));
}
// This code is contributed by lokeshpotta20
Java
// Java program for the above approach
import java.io.*;
class GFG{
// This function is used to find
// minimum distance between same
// repeating characters
static int shortestDistance(String S, int N)
{
// Store minimum distance between same
// repeating characters
int minDis = S.length();
// For loop to consider each element
// of string
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// Comparison of string characters and
// updating the minDis value
if (S.charAt(i) == S.charAt(j) &&
(j - i) < minDis)
{
minDis = j - i;
// As this value would be least
// therefore break
break;
}
}
}
// If minDis value is not updated that means
// no repeating characters
if (minDis == S.length())
return -1;
// Minimum distance is minDis - 1
else
return minDis - 1;
}
// Driver code
public static void main(String[] args)
{
// Given input
String S = "geeksforgeeks";
int N = 13;
// Function call
System.out.println(shortestDistance(S, N));
}
}
// This code is contributed by MuskanKalra1
Python3
# Python3 implementation of above approach # This function is used to find # minimum distance between same # repeating characters def shortestDistance(S, N): # Store minimum distance between same # repeating characters minDis = len(S) # For loop to consider each element of string for i in range(N): for j in range(i+1, N): # Comparison of string characters and # updating the minDis value if(S[i] == S[j] and (j-i) < minDis): minDis = j-i # As this value would be least therefore break break # If minDis value is not updated that means # no repeating characters if(minDis == len(S)): return -1 else: # Minimum distance is minDis - 1 return minDis - 1 # Driver Code # Given Input S = "geeksforgeeks" N = 13 # Function Call print(shortestDistance(S, N))
C#
// C# program for the above approach
using System;
class GFG{
// This function is used to find
// minimum distance between same
// repeating characters
static int shortestDistance(string S, int N)
{
// Store minimum distance between same
// repeating characters
int minDis = S.Length;
// For loop to consider each element
// of string
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// Comparison of string characters and
// updating the minDis value
if (S[i] == S[j] && (j - i) < minDis)
{
minDis = j - i;
// As this value would be least
// therefore break
break;
}
}
}
// If minDis value is not updated that means
// no repeating characters
if (minDis == S.Length)
return -1;
// Minimum distance is minDis - 1
else
return minDis - 1;
}
// Driver code
public static void Main(String[] args)
{
// Given input
string S = "geeksforgeeks";
int N = 13;
// Function call
Console.Write(shortestDistance(S, N));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// This function is used to find
// minimum distance between same
// repeating characters
function shortestDistance( S, N)
{
// Store minimum distance between same
// repeating characters
var minDis = S.length;
// For loop to consider each element
// of string
for(var i = 0; i < N; i++)
{
for(var j = i + 1; j < N; j++)
{
// Comparison of string characters and
// updating the minDis value
if (S.charAt(i) == S.charAt(j) &&
(j - i) < minDis)
{
minDis = j - i;
// As this value would be least
// therefore break
break;
}
}
}
// If minDis value is not updated that means
// no repeating characters
if (minDis == S.length)
return -1;
// Minimum distance is minDis - 1
else
return minDis - 1;
}
// Driver code
// Given input
var S = "geeksforgeeks";
var N = 13;
// Function call
document.write(shortestDistance(S, N));
// This code is contributed by shivanisinghss2110
</script>
Producción
0
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver utilizando Dictionary o Hashing . Primero, almacene el último índice contra el carácter del diccionario para que pueda restarse con el último valor almacenado contra el mismo carácter en el diccionario y luego almacene la distancia en la lista. Al final devuelve el mínimo de la lista. Siga los pasos a continuación para resolver este problema:
- Inicialice un dic de diccionario para almacenar la última aparición del carácter y una lista dis para almacenar la distancia.
- Iterar en el rango [0, N-1] usando la variable i :
- Si el carácter está presente en el diccionario:
- Luego, extraiga su último valor dic[S[i]] y actualícelo con la posición actual i.
- Almacene la diferencia en una variable var = i – dic[S[i]] y agréguela a la lista dis.
- Si el carácter no está presente, inicialice con la posición actual.
- Si el carácter está presente en el diccionario:
- Si la longitud de dis es 0 , eso significa que no hay caracteres repetidos, devuelva -1; de lo contrario, devuelva min(dis) – 1.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// This function is used to find minimum distance between
// same repeating characters
int shortestDistance(string s, int n)
{
// Define a map and an vector
map<char, int> m;
vector<int> v;
// Temporary variable
int var;
// Traverse through string
for (int i = 0; i < n; i++)
{
// If character present in map
if (m.find(s[i]) != m.end())
{
// Difference between current position and last
// stored value
var = i - m[s[i]];
// Updating current position
m[s[i]] = i;
// Storing difference in list
v.push_back(var);
}
// If character not in map assign it with
// initial of its position
else
m[s[i]] = i;
}
// If no element inserted in vector
// i.e. no repeating characters
if (v.size() == 0)
return -1;
sort(v.begin(), v.end());
return v[0] - 1;
}
int main()
{
string s;
s = "geeksforgeeks";
int n = 13;
// Function call
cout << (shortestDistance(s, n));
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG{
// This function is used to find
// minimum distance between same
// repeating characters
static int shortestDistance(String S, int N)
{
// Define a hashmap and an arraylist
HashMap<Character,
Integer> dic = new HashMap<Character,
Integer>();
ArrayList<Integer> dis = new ArrayList<>();
// Temporary variable
int var;
// Traverse through string
for(int i = 0; i < N; i++)
{
// If character present in dictionary
if (dic.get(S.charAt(i)) != null)
{
// Difference between current position
// and last stored value
var = i - dic.get(S.charAt(i));
// Updating current position
dic.put(S.charAt(i), i);
// Storing difference in list
dis.add(var);
}
// If character not in dictionary assign
// it with initial of its position
else
{
dic.put(S.charAt(i), i);
}
}
// If no element inserted in list
// i.e. no repeating characterss
if (dis.size() == 0)
return -1;
// Return minimum distance
else
return Collections.min(dis) - 1;
}
// Driver code
public static void main(String[] args)
{
// Given input
String S = "geeksforgeeks";
int N = 13;
// Function call
System.out.println(shortestDistance(S, N));
}
}
// This code is contributed by MuskanKalra1
Python3
# Python3 implementation of above approach
# This function is used to find the
# required the minimum distances of
# repeating characters
def shortestDistance(S, N):
# Define dictionary and list
dic = {}
dis = []
# Traverse through string
for i in range(N):
# If character present in dictionary
if S[i] in dic:
# Difference between current position
# and last stored value
var = i- dic[S[i]]
# Updating current position
dic[S[i]] = i
# Storing difference in list
dis.append(var)
# If character not in dictionary assign
# it with initial of its position
else:
dic[S[i]] = i
# If no element inserted in list
# i.e. no repeating characters
if(len(dis) == 0):
return -1
# Return minimum distance
else:
return min(dis)-1
# Driver code
# Given Input
S = "geeksforgeeks"
N = 13
# Function Call
print(shortestDistance(S, N))
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
public class GFG {
// This function is used to find
// minimum distance between same
// repeating characters
static int shortestDistance(String S, int N) {
// Define a hashmap and an arraylist
Dictionary<char, int> dic = new Dictionary<char, int>();
List<int> dis = new List<int>();
// Temporary variable
int var;
// Traverse through string
for (int i = 0; i < N; i++) {
// If character present in dictionary
if (dic.ContainsKey(S[i])) {
// Difference between current position
// and last stored value
var = i - dic[S[i]];
// Updating current position
dic[S[i]]= i;
// Storing difference in list
dis.Add(var);
}
// If character not in dictionary assign
// it with initial of its position
else {
dic.Add(S[i], i);
}
}
dis.Sort();
// If no element inserted in list
// i.e. no repeating characterss
if (dis.Count == 0)
return -1;
// Return minimum distance
else
return dis[0]- 1;
}
// Driver code
public static void Main(String[] args) {
// Given input
String S = "geeksforgeeks";
int N = 13;
// Function call
Console.WriteLine(shortestDistance(S, N));
}
}
// This code contributed by umadevi9616
Javascript
<script>
// javascript implementation of above approach
// This function is used to find
// minimum distance between same
// repeating characters
function shortestDistance( S , N) {
// Define a hashmap and an arraylist
var dic = new Map();
var dis = new Array();
// Temporary variable
var var1;
// Traverse through string
for (i = 0; i < N; i++) {
// If character present in dictionary
if (dic[S[i]] != null) {
// Difference between current position
// and last stored value
var1 = i - dic[S[i]];
// Updating current position
dic[S[i]] = i;
// Storing difference in list
dis.push(var1);
}
// If character not in dictionary assign
// it with initial of its position
else {
dic[S[i]]= i;
}
}
// If no element inserted in list
// i.e. no repeating characterss
if (dis.length == 0)
return -1;
// Return minimum distance
else
return dis.reduce(function(previous,current){
return previous < current ? previous:current
}) - 1;
}
// Driver code
// Given input
var S = "geeksforgeeks";
var N = 13;
// Function call
document.write(shortestDistance(S, N));
// This code is contributed by gauravrajput1
</script>
Producción
0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
AlternoSolución: El siguiente problema también podría resolverse utilizando un enfoque mejorado de dos puntos. Básicamente, la idea es mantener un puntero izquierdo para cada carácter y, tan pronto como se repita ese carácter en particular, el puntero izquierdo apunta al índice más cercano del carácter. Mientras hacemos esto, podemos mantener una variable ans que almacenará la distancia mínima entre dos caracteres duplicados. Esto podría lograrse utilizando una array de vectores visitada que almacenará el índice más cercano de un carácter actual en la array.
Siga los pasos a continuación para resolver este problema:
- Inicialice un vector visitado para almacenar el último índice de cualquier carácter (puntero izquierdo)
- Iterar en el rango [0, N-1]:
- Si el personaje es visitado previamente:
- Encuentre la distancia entre los caracteres y verifique si la distancia entre los dos es mínima.
- Si es menor que el mínimo anterior, actualice su valor.
- Actualice el último índice del carácter actual en la array visitada.
Si no se obtiene una distancia mínima (es decir, cuando el valor de ans es INT_MAX), eso significa que no hay caracteres repetidos. En este caso devuelve -1;
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the minimum distance between two
// repeating characters in a string using two pointers technique
#include <bits/stdc++.h>
using namespace std;
// This function is used to find
// minimum distance between any two
// repeating characters
// using two - pointers and hashing technique
int shortestDistance(string s, int n) {
// hash array to store character's last index
vector<int> visited(128, -1);
int ans = INT_MAX;
// Traverse through the string
for(int right = 0; right < n; right++) {
char c = s[right];
int left = visited;
// If the character is present in visited array
// find if its forming minimum distance
if(left != -1)
ans = min(ans, right - left -1);
// update current character's last index
visited = right;
}
// Return minimum distance found, else -1
return ans == INT_MAX ? -1 : ans;
}
int main(){
// Given Input
string s = "geeksforgeeks";
int n = 13;
// Function Call
cout << (shortestDistance(s, n));
}
Java
// Java Program to find the minimum distance between two
// repeating characters in a String using two pointers
// technique
import java.util.*;
class GFG {
// This function is used to find
// minimum distance between any two
// repeating characters
// using two - pointers and hashing technique
static int shortestDistance(String s, int n)
{
// hash array to store character's last index
int[] visited = new int[128];
Arrays.fill(visited, -1);
int ans = Integer.MAX_VALUE;
// Traverse through the String
for (int right = 0; right < n; right++) {
char c = s.charAt(right);
int left = visited;
// If the character is present in visited array
// find if its forming minimum distance
if (left != -1)
ans = Math.min(ans, right - left - 1);
// update current character's last index
visited = right;
}
// Return minimum distance found, else -1
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// Driver code
public static void main(String[] args)
{
// Given Input
String s = "geeksforgeeks";
int n = 13;
// Function Call
System.out.print(shortestDistance(s, n));
}
}
// This code is contributed by umadevi9616
Python3
# Python Program to find the minimum distance between two # repeating characters in a String using two pointers # technique import sys # This function is used to find # minimum distance between any two # repeating characters # using two - pointers and hashing technique def shortestDistance(s, n): # hash array to store character's last index visited = [-1 for i in range(128)]; ans = sys.maxsize; # Traverse through the String for right in range(n): c = (s[right]); left = visited[ord(c)]; # If the character is present in visited array # find if its forming minimum distance if (left != -1): ans = min(ans, right - left - 1); # update current character's last index visited[ord(c)] = right; # Return minimum distance found, else -1 if(ans == sys.maxsize): return -1; else: return ans; # Driver code if __name__ == '__main__': # Given Input s = "geeksforgeeks"; n = 13; # Function Call print(shortestDistance(s, n)); # This code is contributed by umadevi9616
C#
// C# Program to find the minimum distance between two
// repeating characters in a String using two pointers
// technique
using System;
public class GFG {
// This function is used to find
// minimum distance between any two
// repeating characters
// using two - pointers and hashing technique
static int shortestDistance(string s, int n)
{
// hash array to store character's last index
int[] visited = new int[128];
for(int i = 0; i < 128; i++)
visited[i] = -1;
int ans = int.MaxValue;
// Traverse through the String
for (int right = 0; right < n; right++) {
char c = s[right];
int left = visited;
// If the character is present in visited array
// find if its forming minimum distance
if (left != -1)
ans = Math.Min(ans, right - left - 1);
// update current character's last index
visited = right;
}
// Return minimum distance found, else -1
return ans == int.MaxValue ? -1 : ans;
}
// Driver code
public static void Main(String[] args)
{
// Given Input
string s = "geeksforgeeks";
int n = 13;
// Function Call
Console.Write(shortestDistance(s, n));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript Program to find the minimum distance between two
// repeating characters in a String using two pointers
// technique
// This function is used to find
// minimum distance between any two
// repeating characters
// using two - pointers and hashing technique
function shortestDistance(s , n) {
// hash array to store character's last index
var visited = Array(128).fill(-1);
var ans = Number.MAX_VALUE;
// Traverse through the String
for (var right = 0; right < n; right++) {
var left = visited[s.charCodeAt(right)];
// If the character is present in visited array
// find if its forming minimum distance
if (left != -1)
ans = Math.min(ans, right - left - 1);
// update current character's last index
visited[s.charCodeAt(right)] = right;
}
// Return minimum distance found, else -1
return ans == Number.MAX_VALUE ? -1 : ans;
}
// Driver code
// Given Input
var s = "geeksforgeeks";
var n = 13;
// Function Call
document.write(shortestDistance(s, n));
// This code is contributed by umadevi9616
</script>
Producción
0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por chauhanvirat13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA