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:

• Initializing the variable, let's say first, with the i-th bit of the first one checks whether the character (i + 'a') exists at least once in the string or not.
• Initialize a variable, say a second, where the i-th bit of the second checks whether the character (i + 'a') exists at least twice in the string or not.
• Iterating over the character string. For every i-th character, check whether str[i] already appears in the string or not. If true then put the second (str[i] - 'a') of the second.
• Otherwise, set (str[i] - 'a') bit to first.
• Finally, iterate over the range [0, 25] and check if the i-th bit of the first and second is set or not. If true, print (i + 'a').

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