Reverse a string

Solution #1: 
If extra space is available then copy the string in reverse order to a newly allocated string in O(n) time.

Solution #2: 
Again, if extra space is permissible then we can use a stack to first push the entire string on the stack and then pop it in reverse order.

Solution #3: 
If it has to be done in place, then we can take two pointers at the start and end of the string and can swap the characters they point to while incrementing and decrementing them respectively till they collide.

Solution #4: 
Approach three can also be done recursively as follows

void reverse(char *start, char *end)
{
    char temp;

    if(start >= end)
        return;
    
    temp = start[0];
    start[0] = end[0];
    end[0] = temp;

    reverse(start+1, end-1);    
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    int len;

    gets(str);
    len = strlen(str);

    reverse(str, str+len-1);

    printf("%s\n", str);

    return 1;
}

Check whether a string is a rotation of another string or not

The first thing, of course, would be to make sure that both the strings have same length. 

Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego"). 

Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

Anagrams

Find whether two words are anagrams (cafe / face)

• Go to first word in hash table, add 1 in hash table then see whether all letters of 2nd word also in hash table, if it reaches end of 2nd word it means it is a anagram. Issue: 2 same letters in the word
• Increment values in the hash table instead of storing 1 for the first word & then for the 2nd word, decrement values, if all values 0 at the end of 2nd word - it means anagram Complexity = 3n (parse 1st word, parse 2nd word, parse the array)

Create sets of anagrams from a word list (cafe, face, fdga, dgfa - you you will have 2 lists => cafe/face & fdga/dgfa)

• Go to first word, see if any lists, if a list take a word from that list & run the above function for that two words, if return true then add to that list, if false do this for all the lists, create a new list with that word is still that word not in any list Complexity = l * 3n * x (l-no of words, x-no of unique lists)
• sort each word & sort list & then group
• aefc, aefc, adfg, adfg
• Complexity =>
• sorting = nlogn
• sorting each word = nlogn * size of each word
• sorting list = l*log l * total no of words
• total complexity = sorting each word + sorting list + grouping

Longest Palindromic Substring

Easy but invalid solution:

Reverse S and become S’.

This seemed to work, let’s see some examples below.

For example,

S = “caba”, S’ = “abac”.

The longest common substring between S and S’ is “aba”, which is the answer.

Let’s try another example:

S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.

The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us a O(N²) DP solution which uses O(N²) space.

Correct Solution

Print all permutations of a string

permute("123", 0, 3);

function permute($str, $start, $strLength) {
  if ($start === $strLength) {
    var_dump($str);
    return;
  }
  for ($i=$start; $i<$strLength; $i++) {
    swap($str, $i, $start);
    permute($str, $start+1, $strLength);
    swap($str, $start, $i);
  }
}
 
function swap(&$str, $pos1, $pos2) { 
  $tmp = $str[$pos1]; 
  $str[$pos1] = $str[$pos2]; 
  $str[$pos2] = $tmp; 
}

Print all possible combinations of strings that can be made using a keypad given a number

telKeys("2133004655", "2133004655", 0, 10);

$keypad = array("ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ");
function telKeys($original, $new, $start, $strLength) {
  global $keypad;
  if ($start === $strLength) {
    var_dump($new);
    return;
  }

    $new[$start] = $keypad[$original[$start]][0];
    telKeys($original, $new, $start+1, $strLength);
    
    $new[$start] = $keypad[($original[$start])][1];
    telKeys($original, $new, $start+1, $strLength);
    
    if(($original[$start]) < 8) {
        $new[$start] = $keypad[($original[$start])][2];
        telKeys($original, $new, $start+1, $strLength);
    }
}

Print given string in all combinations of uppercase and lowercasecharacters

Given a string we need to print the string with all possible combinations of the uppercase and lowercase characters in the string.

So given a string "abc", we need to print the following:
ABC
ABc
AbC
Abc
aBC
aBc
abC
abc

Solution is a simple recursive approach where we call the function again and again once with a character in lower case and another time with the same character in upper case. The code is similar to what we would write for all permutations of a string.

lowerUpper("abc", 0, 3);

function lowerUpper($str, $start, $strLength) {
  if ($start === $strLength) {
    var_dump($str);
    return;
  }
    
  $str[$start] = strtoupper($str[$start]);
  lowerUpper($str, $start+1, $strLength);
    
  $str[$start] = strtolower($str[$start]);
  lowerUpper($str, $start+1, $strLength);
}

Print every word that is an anagram of another word in the dictionary

An anagram is any word that rearranges the letters of another word to form itself. For example, “act” and “cat” are anagrams of each other, as well as “admirer” and “married”.

Easy Solution

Compare each word against every other word in the dictionary, checking if they are anagrams of each other by sorting by character and testing for equality. This requires O(n^2) and is a working solution.

Efficient Solution

Example dictionary: {cat, dog, sad, act, cab, mat, god }
--- Sort each word only once, saving it into a temporary copy of the dictionary
Copy dictionary and sort by character: { act, dgo, ads, act, abc, amt, dgo }

Flow 1:

Use a Hashtable with hash(eachWord) as key & count as value, if count > 1 it means there is an anagram creation of the hashtable is n*mLogm (m is the average number of letters in a word and n is the total number of words in the dictionary)

Flow 2: 

We can take it one step further and gain real savings from sorting the temporary copy as well, which only costs O(n log n). It then allows you to find anagrams in O(n) time by going down the list and checking neighbors for equality. However, you’ll have to store the index into the original dictionary of the word as well since they’ll get rearranged.

Example dictionary: {cat, dog, sad, act, cab, mat, god }
Copy dictionary along with index and sort by character:
{ (act 0), (dgo 1), (ads 2), (act 3), (abc 4), (amt 5), (dgo 6) }
Sort dictionary: { (abc 4), (act 0), (act 3), (ads 2), (amt 5), (dgo 1), (dgo 6) }
Go through and find matching neighbors, extracting their indices and printing the corresponding word in the dictionary: 0, 3, 1, 6 -> cat act dog god