Strings

Question 1

check if two strings are Anagrams

Answer 1

Use a hash table to store frequency of first string, then decrement frequency using second string, if finally hash is not zero then the strings are not anagrams.

Question 2

Find leftmost character that repeats in string

Answer 2

Best way is to iterate the list from back and maintain a recent variable to store the index of the latest encountered repeating character. To track if character is repeating, use a hash of indices initialized to -1.
Keep storing indices for newly encountered element.

Finally return the a[recent]

Question 3

Find leftmost non-repeating character in string

Answer 3

Use hash table initialized to -1 to store indices. We will use -2 in hash table to indicate that a character is repeating otherwise store the index of the newly encountered element.

Then traverse the hash table to find the element with least index and return.

Question 4

Check if two strings are rotations of one another

Answer 4

Idea is to concatenate the one string with itself, then find if the second string is present.

if(s1.size() != s2.size()){
return false;
}

string temp = s1 + s1;

if(temp.find(s2) != string::npos)
    return true;

Question 5

Naive Pattern Match

Answer 5

Simply compare each character of pattern with text iteratively. Time: O(m-n)*m. If pattern has distinct characters, then shift i by j.

for i in range(n-m+1):
        j=0
        while j < m:            
            if(p[j] != s[i+j]):
                break
            j+=1            
        if j == m:
            return True
return False

Question 6

Rabin Karp Algorithm

Answer 6

We compute hash of pattern first and then compare it with hash of sliding window. If the hash match, then we compare the characters. This saves time since we can compute rolling hash. We also need a better hash function to avoid spurious hits ( same hash for different permutations).
One way to compute hash is using fn below:
t_i+1 = d(t_i - txt[i]*d^(m-1)) + txt[i+m]
where d =base (5) and m is pattern length.

We use Horner’s rule to compute hash: h = 0
h = (h*d + pat[i] ) % q ( q is a large prime number)
if h becomes < 0 then add q to it.

Time: O(n-m+1 * m) worse, avg : linear

Application: Used when we need to find multiple occurrences of pattern in a text.

Question 7

Isomorphic strings

Answer 7

1-to-1 mapping in 2 strings like s=’aab’ and p=’xxy’. Thing to note here is that in addition to maintain a mapping for ‘s’ to ‘p’, we also need to maintain a set of visited characters in ‘p’ for cases like ‘xyz’ and ‘aba’.