Dada una string, encuentre el número máximo de caracteres entre dos caracteres en la string. Si no se repite ningún carácter, imprima -1.
Ejemplos:
Input : str = "abba" Output : 2 The maximum number of characters are between two occurrences of 'a'. Input : str = "baaabcddc" Output : 3 The maximum number of characters are between two occurrences of 'b'. Input : str = "abc" Output : -1
Enfoque 1 (simple): use dos bucles anidados. El ciclo externo selecciona caracteres de izquierda a derecha, el ciclo interno encuentra la ocurrencia más lejana y realiza un seguimiento del máximo.
C++
// Simple C++ program to find maximum number
// of characters between two occurrences of
// same character
#include <bits/stdc++.h>
using namespace std;
int maximumChars(string& str)
{
int n = str.length();
int res = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (str[i] == str[j])
res = max(res, abs(j - i - 1));
return res;
}
// Driver code
int main()
{
string str = "abba";
cout << maximumChars(str);
return 0;
}
Java
// Simple Java program to find maximum
// number of characters between two
// occurrences of same character
class GFG {
static int maximumChars(String str)
{
int n = str.length();
int res = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (str.charAt(i) == str.charAt(j))
res = Math.max(res,
Math.abs(j - i - 1));
return res;
}
// Driver code
public static void main(String[] args)
{
String str = "abba";
System.out.println(maximumChars(str));
}
}
// This code is contributed by vt_m.
Python3
# Simple Python3 program to find maximum number # of characters between two occurrences of # same character def maximumChars(str): n = len(str) res = -1 for i in range(0, n - 1): for j in range(i + 1, n): if (str[i] == str[j]): res = max(res, abs(j - i - 1)) return res # Driver code if __name__ == '__main__': str = "abba" print(maximumChars(str)) # This code is contributed by PrinciRaj1992
C#
// Simple C# program to find maximum
// number of characters between two
// occurrences of same character
using System;
public class GFG {
static int maximumChars(string str)
{
int n = str.Length;
int res = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (str[i] == str[j])
res = Math.Max(res,
Math.Abs(j - i - 1));
return res;
}
// Driver code
static public void Main ()
{
string str = "abba";
Console.WriteLine(maximumChars(str));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Simple Javascript program to find maximum
// number of characters between two
// occurrences of same character
function maximumChars(str)
{
let n = str.length;
let res = -1;
for (let i = 0; i < n - 1; i++)
for (let j = i + 1; j < n; j++)
if (str[i] == str[j])
res = Math.max(res,
Math.abs(j - i - 1));
return res;
}
// Driver code
let str = "abba";
document.write(maximumChars(str));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad de tiempo: O (n ^ 2)
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Enfoque 2 (eficiente): inicialice una array «FIRST» de longitud 26 en la que tenemos que almacenar la primera aparición de un alfabeto en la string y otra array «LAST» de longitud 26 en la que almacenaremos la última aparición del alfabeto en la cuerda. Aquí, el índice 0 corresponde al alfabeto a, el 1 al b y así sucesivamente. Después de eso, tomaremos la diferencia entre la última y la primera array para encontrar la diferencia máxima si no están en la misma posición.
C++
// Efficient C++ program to find maximum number
// of characters between two occurrences of
// same character
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
int maximumChars(string& str)
{
int n = str.length();
int res = -1;
// Initialize all indexes as -1.
int firstInd[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
firstInd[i] = -1;
for (int i = 0; i < n; i++) {
int first_ind = firstInd[str[i]];
// If this is first occurrence
if (first_ind == -1)
firstInd[str[i]] = i;
// Else find distance from previous
// occurrence and update result (if
// required).
else
res = max(res, abs(i - first_ind - 1));
}
return res;
}
// Driver code
int main()
{
string str = "abba";
cout << maximumChars(str);
return 0;
}
Java
// Efficient java program to find maximum
// number of characters between two
// occurrences of same character
import java.io.*;
public class GFG {
static int MAX_CHAR = 256;
static int maximumChars(String str)
{
int n = str.length();
int res = -1;
// Initialize all indexes as -1.
int []firstInd = new int[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
firstInd[i] = -1;
for (int i = 0; i < n; i++)
{
int first_ind = firstInd[str.charAt(i)];
// If this is first occurrence
if (first_ind == -1)
firstInd[str.charAt(i)] = i;
// Else find distance from previous
// occurrence and update result (if
// required).
else
res = Math.max(res, Math.abs(i
- first_ind - 1));
}
return res;
}
// Driver code
static public void main (String[] args)
{
String str = "abba";
System.out.println(maximumChars(str));
}
}
// This code is contributed by vt_m.
Python3
# Efficient Python3 program to find maximum # number of characters between two occurrences # of same character MAX_CHAR = 256 def maximumChars(str1): n = len(str1) res = -1 # Initialize all indexes as -1. firstInd = [-1 for i in range(MAX_CHAR)] for i in range(n): first_ind = firstInd[ord(str1[i])] # If this is first occurrence if (first_ind == -1): firstInd[ord(str1[i])] = i # Else find distance from previous # occurrence and update result (if # required). else: res = max(res, abs(i - first_ind - 1)) return res # Driver code str1 = "abba" print(maximumChars(str1)) # This code is contributed by Mohit kumar 29
C#
// Efficient C# program to find maximum
// number of characters between two
// occurrences of same character
using System;
public class GFG {
static int MAX_CHAR = 256;
static int maximumChars(string str)
{
int n = str.Length;
int res = -1;
// Initialize all indexes as -1.
int []firstInd = new int[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
firstInd[i] = -1;
for (int i = 0; i < n; i++)
{
int first_ind = firstInd[str[i]];
// If this is first occurrence
if (first_ind == -1)
firstInd[str[i]] = i;
// Else find distance from previous
// occurrence and update result (if
// required).
else
res = Math.Max(res, Math.Abs(i
- first_ind - 1));
}
return res;
}
// Driver code
static public void Main ()
{
string str = "abba";
Console.WriteLine(maximumChars(str));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Efficient javascript program to find maximum
// number of characters between two
// occurrences of same character
let MAX_CHAR = 256;
function maximumChars(str)
{
let n = str.length;
let res = -1;
// Initialize all indexes as -1.
let firstInd = new Array(MAX_CHAR);
for (let i = 0; i < MAX_CHAR; i++)
firstInd[i] = -1;
for (let i = 0; i < n; i++)
{
let first_ind = firstInd[str[i].charCodeAt(0)];
// If this is first occurrence
if (first_ind == -1)
firstInd[str[i].charCodeAt(0)] = i;
// Else find distance from previous
// occurrence and update result (if
// required).
else
res = Math.max(res, Math.abs(i
- first_ind - 1));
}
return res;
}
// Driver code
let str = "abba";
document.write(maximumChars(str));
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad de tiempo : O(n)
Espacio Auxiliar: O(256)
Este artículo es una contribución de Aarti_Rathi y UDIT UPADHYAY . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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