SDE - 1

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections: 
a[1..Lo-1] zeroes (red)
a[Lo..Mid-1] ones (white)
a[Mid..Hi] unknown
a[Hi+1..N] twos (blue)
If the ith element is 0 then swap the element to the low range, thus shrinking the unknown range.
Similarly, if the element is 1 then keep it as it is but shrink the unknown range.
If the element is 2 then swap it with an element in high range.

Keep three indices low = 1, mid = 1 and high = N and there are four ranges, 1 to low (the range containing 0), low to mid (the range containing 1), mid to high (the range containing unknown elements) and high to N (the range containing 2).
Traverse the array from start to end and mid is less than high. (Loop counter is i)
If the element is 0 then swap the element with the element at index low and update low = low + 1 and mid = mid + 1
If the element is 1 then update mid = mid + 1
If the element is 2 then swap the element with the element at index high and update high = high – 1 and update i = i – 1. As the swapped element is not processed
Print the array.

Time Complexity: O(n). 
Only one traversal of the array is needed.
Space Complexity: O(1). 
No extra space is required.

Start from the leftmost character and remove duplicates at left corner if there are any.
The first character must be different from its adjacent now. Recur for string of length n-1 (string without first character).
Let the string obtained after reducing right substring of length n-1 be rem_str. There are three possible cases 
If first character of rem_str matches with the first character of original string, remove the first character from rem_str.
If remaining string becomes empty and last removed character is same as first character of original string. Return empty string.
Else, append the first character of the original string at the beginning of rem_str.
Return rem_str.

The time complexity of the solution can be written as T(n) = T(n-k) + O(k) where n is length of the input string and k is the number of first characters which are same. Solution of the recurrence is O(n)

This method assumes that the set of possible characters in both strings is small. In the following implementation, it is assumed that the characters are stored using 8 bit and there can be 256 possible characters. 

Create count arrays of size 256 for both strings. Initialize all values in count arrays as 0.
Iterate through every character of both strings and increment the count of character in the corresponding count arrays.
Compare count arrays. If both count arrays are same, then return true.

The longest common prefix for an array of strings is the common prefix between 2 most dissimilar strings. For example, in the given array {“apple”, “ape”, “zebra”}, there is no common prefix because the 2 most dissimilar strings of the array “ape” and “zebra” do not share any starting characters.
Time Complexity: O(MAX * n * log n ) where n is the number of strings in the array and MAX is maximum number of characters in any string. Please note that comparison of two strings would take at most O(MAX) time and for sorting n strings, we would need O(MAX * n * log n ) time.