Given a string str, the task is to find all repeated characters in the given string in lexicographic order without using any additional data structure.
Examples:
Input: str = “geeksforgeeks” Output: e g k s Explanation: Frequency of character ‘g’ = 2 Frequency of character ‘e’ = 4 Frequency of character ‘k’ = 2 Frequency of character ‘s’ = 2 Therefore, the required output is e g k s. Input: str = “apple” Output: p Explanation: Frequency of character ‘p’ = 2. Therefore, the required output is p.
Approach: Follow the steps below to solve the problem:
Below is the implementation of the above approach:
// 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.
Output:
e g k s