Encuentre el primer carácter repetido en una cadena en C++

1. Encuentra el primer carácter repetido en una cadena en C++
2. Use la técnica Hashing para encontrar el primer carácter repetido en una cadena en C++
3. Use el método de fuerza bruta para encontrar el primer carácter repetido en una cadena en C++

En este tutorial, aprenderá cómo encontrar el primer carácter repetido en una cadena en C++. Aprenderá tres enfoques para cumplir con este propósito: la técnica hash, el método de fuerza bruta y la escritura de su algoritmo.

Encuentra el primer carácter repetido en una cadena en C++

Hay dos enfoques para intentar escribir sus algoritmos; el primero consiste en recorrer la cadena de izquierda a derecha, y el segundo enfoque consiste en recorrer la cadena de derecha a izquierda y realizar un seguimiento de los caracteres visitados. El segundo enfoque es superior en rendimiento a cualquier otro porque es más eficiente al hacer menos comparaciones.

Los algoritmos de clasificación pueden ayudarlo a encontrar el primer carácter repetido en una cadena en el tiempo O(n Log n). Sin embargo, puede recorrer la cadena y codificar los caracteres utilizando códigos ASCII, ejecutar el bucle en la matriz hash y encontrar la posición mínima de cualquier carácter repetido.

Ejemplo de código:

#include <iostream>

using namespace std;

#define numberChar 256

// left most string
int farLeftStr(string& primeStr) {
  // represents the first index
  int IndexNum[numberChar];

  for (int i = 0; i < numberChar; i++) IndexNum[i] = -1;

  // represents the resultIndexNum
  int resultStr = INT_MAX;

  for (int i = 0; i < primeStr.length(); i++) {
    if (IndexNum[primeStr[i]] == -1)
      IndexNum[primeStr[i]] = i;
    else
      resultStr = min(resultStr, IndexNum[primeStr[i]]);
  }
  return (resultStr == INT_MAX) ? -1 : resultStr;
}

int main() {
  string primeStr = "HouseOfTheDragons";
  int left = farLeftStr(primeStr);

  if (left == -1)
    cout << "All characters are distinct or string is empty ";
  else
    cout << "The first repeating character is: " << primeStr[left];
  return 0;
}

Producción :

The first repeating character is: o

Atravesar una cadena de izquierda a derecha es factible inicializando el primer índice de cada carácter como -1. Puede comparar el primer índice o el más a la izquierda de un carácter repetido (en caso de que lo encuentre) con el resultado actual.

Además, puedes usar la complejidad O(N²) para resolver este problema estudiando cada carácter y buscándolo en el resto de la cadena.

Use la técnica Hashing para encontrar el primer carácter repetido en una cadena en C++

Una matriz Count puede encontrar el primer carácter repetido y mantener un recuento de caracteres repetidos en una cadena.

La técnica de hashing consta de cuatro pasos principales.

1. Crear una tabla hash.
2. Escaneo de caracteres.
3. Inserte un carácter en la tabla hash si no está presente.
4. De lo contrario, devolver ese carácter como un duplicado.

Ejemplo de código:

#include <iostream>

// hashing function object type
#include <unordered_set>

using namespace std;

char getRepeatingChar(string &str) {
  unordered_set<char> hashObj;

  for (int i = 0; i < str.length(); i++) {
    char repChar = str[i];
    if (hashObj.find(repChar) != hashObj.end())
      return repChar;
    else
      hashObj.insert(repChar);
  }
  return '\0';
}

int main() {
  string expStr = "GameOfThrones";
  cout << "The first repeating character is: " << getRepeatingChar(expStr);
}

Producción :

The first repeating character is: e

Otra variación famosa de este problema es imprimir el primer carácter único o no repetitivo en una cadena al imprimir los resultados si el Cuenta es igual a uno. Es posible imprimir todos los caracteres repetidos en una cadena como una variación extendida de la técnica original, pero no es tan sencillo como el método hash básico.

Como se requiere que el usuario cree la matriz Count, la complejidad de tiempo de este método será O(n). En el peor de los casos, sin repetición y con espacio extra, su complejidad temporal será O(1).

Use el método de fuerza bruta para encontrar el primer carácter repetido en una cadena en C++

Es un método simple que permite a los programadores verificar cada carácter de una cadena para encontrar un carácter repetido y generar los resultados correspondientes. Si se alcanza la cadena final o se escanea el último carácter, no se encuentra ningún carácter repetido y no hay ningún carácter repetido de forma predeterminada.

En el peor de los casos, su complejidad temporal es O(n2) en caso de no repetición, y en el mejor de los casos, es O(1), que representa la presencia de un carácter repetido en la segunda posición. . Como necesita una matriz de conteo que tome una cantidad constante de memoria, es más que el método de fuerza bruta, y el espacio extra total que toma es O(1), es decir, constante.

Ejemplo de código:

#include <iostream>

using namespace std;

int main() {
  string expStr = "Hello World!";
  string primeExp = "";

  // check the boundary of the `expStr` string
  if (expStr == primeExp) {
    cout << "The string is empty!";
  }

  for (int a = 0; expStr[a] != '\0'; a++) {
    for (int b = a + 1; expStr[b] != '\0'; b++) {
      if (expStr[a] == expStr[b]) {
        cout << "The first repeating character is: " << expStr[a];
      }
      break;
    }
  }
}

Producción :

The first repeating character is: l