Given a string s containing only lower case alphabets (a - z), find (i.e print) the characters that are repeated.

For ex, if string s = "aabcacdddec"

Output: a c d

3 approaches to this problem exists:

[brute force] Check every char of string (i.e s[i] with every other char and print if both are same) Time complexity: O(n^2) Space complexity: O(1)

[sort and then compare adjacent elements] After sorting (in O(n log(n) time), traverse the string and check if s[i] ans s[i + 1] are equal Time complexity: O(n logn) + O(n) = O(n logn) Space complexity: O(1)

[store the character count in an array] Create an array of size 26 (to keep track of a - z) and for every s[i], increment value stored at index = s[i] - 26 in the array. Finally traverse the array and print all elements (i.e 'a' + i) with value greater than 1 Time complexity: O(n) Space complexity: O(1) but we have a separate array for storing the frequency of each element.

Is there a O(n) approach that DOES NOT use any array/hash table/map (etc)?

HINT: Use BIT Vectors

## comments: