Dada una string str , la tarea es encontrar todos los caracteres duplicados presentes en una string determinada en orden lexicográfico sin utilizar ninguna estructura de datos adicional.
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: egks
Explicación:
Frecuencia del carácter ‘g’ = 2
Frecuencia del carácter ‘e’ = 4
Frecuencia del carácter ‘k’ = 2
Frecuencia del carácter ‘s’ = 2
Por lo tanto, la salida requerida es huevos _Entrada: str = “manzana”
Salida: p
Explicación:
Frecuencia del carácter ‘p’ = 2.
Por lo tanto, la salida requerida es p .
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos first , donde i th bit of first verifique si el carácter (i + ‘a’) está presente en la string al menos una vez o no.
- Inicialice una variable, digamos segundo, donde el i -ésimo bit del segundo verifica si el carácter (i + ‘a’) está presente en la string al menos dos veces o no.
- Iterar sobre los caracteres de la string . Para cada i -ésimo carácter, compruebe si str[i] ya se ha producido en la string o no. Si se determina que es cierto, establezca el (str[i] – ‘a’) th bit de second .
- De lo contrario, establezca (str[i] – ‘a’) el bit del primero .
- Finalmente, itere sobre el rango [0, 25] y verifique si el i -ésimo bit tanto del primero como del segundo está configurado o no . Si se encuentra que es cierto, imprima (i + ‘a’) .
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 find duplicate characters
// in string without using any additional
// data structure
void findDuplicate(string str, int N)
{
// Check if (i + 'a') is present
// in str at least once or not.
int first = 0;
// Check if (i + 'a') is present
// in str at least twice or not.
int second = 0;
// Iterate over the characters
// of the string str
for (int i = 0; i < N; i++) {
// If str[i] has already occurred in str
if (first & (1 << (str[i] - 'a'))) {
// Set (str[i] - 'a')-th bit of second
second
= second | (1 << (str[i] - 'a'));
}
else {
// Set (str[i] - 'a')-th bit of second
first
= first | (1 << (str[i] - 'a'));
}
}
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++) {
// If i-th bit of both first
// and second is Set
if ((first & (1 << i))
&& (second & (1 << i))) {
cout << char(i + 'a') << " ";
}
}
}
// Driver Code
int main()
{
string str = "geeksforgeeks";
int N = str.length();
findDuplicate(str, N);
}
Java
// Java program for the above approach
public class GFG
{
// Function to find duplicate characters
// in string without using any additional
// data structure
static void findDuplicate(String str, int N)
{
// Check if (i + 'a') is present
// in str at least once or not.
int first = 0;
// Check if (i + 'a') is present
// in str at least twice or not.
int second = 0;
// Iterate over the characters
// of the string str
for (int i = 0; i < N; i++)
{
// If str[i] has already occurred in str
if ((first & (1 << (str.charAt(i) - 'a'))) != 0)
{
// Set (str[i] - 'a')-th bit of second
second
= second | (1 << (str.charAt(i) - 'a'));
}
else
{
// Set (str[i] - 'a')-th bit of second
first
= first | (1 << (str.charAt(i) - 'a'));
}
}
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++)
{
// If i-th bit of both first
// and second is Set
if (((first & (1 << i))
& (second & (1 << i))) != 0) {
System.out.print((char)(i + 'a') + " ");
}
}
}
// Driver Code
static public void main(String args[])
{
String str = "geeksforgeeks";
int N = str.length();
findDuplicate(str, N);
}
}
// This code is contributed by AnkThon.
Python3
# Python 3 code added. program to implement # the above approach # Function to find duplicate characters # in string without using any additional # data structure def findDuplicate(str1, N): # Check if (i + 'a') is present # in str1 at least once or not. first = 0 # Check if (i + 'a') is present # in str1 at least twice or not. second = 0 # Iterate over the characters # of the string str1 for i in range(N): # If str1[i] has already occurred in str1 if (first & (1 << (ord(str1[i]) - 97))): # Set (str1[i] - 'a')-th bit of second second = second | (1 << (ord(str1[i]) - 97)) else: # Set (str1[i] - 'a')-th bit of second first = first | (1 << (ord(str1[i]) - 97)) # Iterate over the range [0, 25] for i in range(26): # If i-th bit of both first # and second is Set if ((first & (1 << i)) and (second & (1 << i))): print(chr(i + 97), end = " ") # Driver Code if __name__ == '__main__': str1 = "geeksforgeeks" N = len(str1) findDuplicate(str1, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find duplicate characters
// in string without using any additional
// data structure
static void findDuplicate(string str, int N)
{
// Check if (i + 'a') is present
// in str at least once or not.
int first = 0;
// Check if (i + 'a') is present
// in str at least twice or not.
int second = 0;
// Iterate over the characters
// of the string str
for (int i = 0; i < N; i++) {
// If str[i] has already occurred in str
if ((first & (1 << (str[i] - 'a'))) != 0)
{
// Set (str[i] - 'a')-th bit of second
second
= second | (1 << (str[i] - 'a'));
}
else
{
// Set (str[i] - 'a')-th bit of second
first
= first | (1 << (str[i] - 'a'));
}
}
// Iterate over the range [0, 25]
for (int i = 0; i < 26; i++)
{
// If i-th bit of both first
// and second is Set
if (((first & (1 << i))
& (second & (1 << i))) != 0) {
Console.Write((char)(i + 'a') + " ");
}
}
}
// Driver Code
static public void Main()
{
string str = "geeksforgeeks";
int N = str.Length;
findDuplicate(str, N);
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// Javascript program for the above approach
// Function to find duplicate characters
// in string without using any additional
// data structure
function findDuplicate(str, N)
{
// Check if (i + 'a') is present
// in str at least once or not.
let first = 0;
// Check if (i + 'a') is present
// in str at least twice or not.
let second = 0;
// Iterate over the characters
// of the string str
for(let i = 0; i < N; i++)
{
// If str[i] has already occurred in str
if ((first & (1 << (str[i].charCodeAt() -
'a'.charCodeAt()))) != 0)
{
// Set (str[i] - 'a')-th bit of second
second = second | (1 << (str[i].charCodeAt() -
'a'.charCodeAt()));
}
else
{
// Set (str[i] - 'a')-th bit of second
first = first | (1 << (str[i].charCodeAt() -
'a'.charCodeAt()));
}
}
// Iterate over the range [0, 25]
for(let i = 0; i < 26; i++)
{
// If i-th bit of both first
// and second is Set
if (((first & (1 << i)) &
(second & (1 << i))) != 0)
{
document.write(String.fromCharCode(
i + 'a'.charCodeAt()) + " ");
}
}
}
// Driver code
let str = "geeksforgeeks";
let N = str.length;
findDuplicate(str, N);
// This code is contributed by divyesh072019
</script>
Producción:
e g k s
Complejidad temporal: O(N)
Espacio auxiliar: O(1)