reversing a string in C++

C++ string does not have reverse member function,
this is how we can do it:

string s("abcdef");
reverse(s.begin(), s.end());

Binary Search of a string

Interesting problem : How can we apply binary search to search a string in a big word file?

We use a suffix array and sort this array. Once sorted, we apply binary search on this array. See Bentley Programming Pearls p.172. See also : Large-scale genome sequence processing By Masahiro Kasahara, Shinichi Morishita, p.56

We can optimize this even further by storing the radix representation of strings (see:Cormen's section in Hashing) and the problem will be reduced to binary search of numbers.

Common characters

Write a function f(a, b) which takes two string arguments and returns a
string containing only the characters found in both strings in the order
of O(n)

Answer:

//Use a lookup table, this can be 
size_t lookup[26];
// or just a unsigned int, in which the first 26 bits 
// is used to mark the presence of a character.
size_t lookup;

Scan the first string and mark the characters in the lookup

Scan the second string, if the character is found in lookup,
then copy it to output string.

Combinations of Brackets

Develop an algorithm to find out all valid combinations of n brackets. Like for n =3 possible combinations can be ((())) or ()()() or (()()) and so on.
Answer:

Use a stack. 
while( not end of input )
{
  ch = input character
  if ( ch is '(' ) then push it to stack.
  else pop from stack., and if the poped item is not '(' then error.
}
The stack should be empty now.

Split a sentence on a word

Token a string on the basis if a given delimiter.
e.g S is the base string and D is the delimiter (could be a sequence of
any valid chars)
S = ["who is the man who saw the eagle today went the wrong way?"]
D = ["the"]
Result = ["who is ", " man who saw ", " eagle today went ", " wrong way?"]

Answer:
Solution 1: Represent the words as a linked list, then when the node does not match
the delimiter, output it. We can use a hash value stored along with the nodes to help in better comparision.

cyclic permutations of a string

Write and algo to check if two strings are cyclic permutations of each other?
Ex : "abcde" and "deabc"

Answer:

1. Append the second the string with itself, we get, deabcdeabc O(n)
2. When we do step 2, notice that the first string occurs as a substring.
3. Search for the original string in the appended string. (O(2n) for space + O(n) time if suffix trees are used and this step depends on which sub string search algo we use)

|---||---|
deabcdeabc
  ^^^^^

Reverse the words in a string

Given an array of characters which form a sentence of words, give an
efficient algorithm to reverse the order of the words (not characters)
in it.

Answer:^[1]

Method 1:
I am a good boy
<------------->

yob doog  a   ma   I
<-> <--> <->  <-> <->

boy good a am I

Method2
Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input  : I am a good boy
                     <--
                <-------
              <---------
           <------------
         <--------------
  

Output : boy
       : boy good
       : boy good a 
       : boy good a am 
       : boy good a am I 


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.


Method3

Create a linked list like


+---+    +----------+    +----+    +----------+    +---+    +----------+ 
| I | -> |  | -> | am | -> |  | -> | a | -> |  | --+
+---+    +----------+    +----+    +----------+    +---+    +----------+   |
                                                                           |
                                                                           |
 +-------------------------------------------------------------------------+
 |
 |     +------+    +----------+    +-----+    +------+
 +---> | good | -> |  | -> | boy | -> | NULL | 
       +------+    +----------+    +-----+    +------+



Now its a simple question of reversing the linked list!. 

Find first non-duplicate character in a string

Find first non-duplicate character in a string.

Solution:

lookup['z'-'a'] = {0}
Pass 1: Traverse the string, and perform ++lookup[string[i]];
Pass 2: Traverse the string, and the first char for which lookup[string[i]] == 1 is the required char.

Finding anagrams

Do do you check if two strings are anagrams??

Answer O(n) solution:

bool lookup[26] = {false}
scan the first string and initialize the lookup
scan the second string and check if all the alpahbets are present.

Find longest run of a letter in a string

Write a function that returns the longest run of a letter in a string. e.g. cccc in the string abccccdef.

Answer:
O(n) solution which sweeps thru the array..

cur next
 |  |
accccefgggggg

GetRepSeq(const char* str, char **start, size_t *len)
{
    const char* next = str + 1;
    const char* cur = str;
    size_t cur_len = 1;
    *start = 0;
    *len = 1;
    while (*next)
    {
        if ( *next == *cur )
        {
            ++next;
            ++cur_len;
        }
        else
        {
            /* we just encountered a non equal char */
            if ( cur_len >= *len )
            {
                *len = cur_len;
                *start = cur;
            }
            cur = next;
            ++next;
        }
    }
}

Alternative Answer : Sufix trees

Longest Panlindrome in a string

Write a function that returns the longest palindrome in a given string. e.g "ccddcc" in the string "abaccddccefe"

Answer (select to see):

Use Suffix trees (http://www.allisons.org/ll/AlgDS/Tree/Suffix/)

Longest common Substring

Given 2 input strings, find the longest string that occurs in both.

Answer (select to see):

Use Suffix trees (http://www.allisons.org/ll/AlgDS/Tree/Suffix/)