Lecture 135:- Finding Duplicates in a String using Bitwise Operations

In C++, you can use bitwise operations to find duplicates in a string by treating each character as a bit and marking the occurrence of characters using bitwise OR operation. However, this approach is limited to strings containing only lowercase English alphabets (a-z) or a specific range of characters. Let's assume we are working with lowercase English alphabets.

Here's a C++ program that demonstrates how to find and print the duplicate characters in a given string using bitwise operations:

cppCopy code

#include <iostream> #include <string> void findDuplicates(const std::string& str) {    int bitVector = 0;    std::cout << "Duplicate characters: ";    for (char c : str) {        int index = c - 'a';        int bit = 1 << index;        if (bitVector & bit) {            // Duplicate character found            std::cout << c << " ";        } else {            // Mark the character as seen using bitwise OR            bitVector |= bit;        }    }    std::cout << std::endl; } int main() {    std::string inputString;    std::cout << "Enter a string: ";    std::getline(std::cin, inputString);    findDuplicates(inputString);    return 0; }

In this program, we use an integer variable bitVector to represent the occurrence of characters. Each character is treated as a bit in the bitVector. When we encounter a character, we calculate its index (0 to 25 for lowercase English alphabets) and set the corresponding bit to 1 using the bitwise OR operation.

If a bit is already set to 1 (indicating that the character has occurred before), it means we have found a duplicate character in the string.

Sample Input:

cCopy code

Enter a string: programming

Sample Output:

yamlCopy code

Duplicate characters: g r m

The program correctly identifies and prints the duplicate characters 'g', 'r', and 'm' in the input string "programming."

Keep in mind that this approach is specific to lowercase English alphabets and may not be suitable for strings containing characters outside this range. For more general cases, using a hash table or other data structures is recommended.