Finding the longest substring in a string without repetition

 

Question

  This is an interesting question shared by my friend. Not so tough. But again, we need to remember the use of bitwise. Read more about here

http://analgorithmaday.blogspot.com/2011/04/unique-items-in-array.html

The question is to find the longest substring in a string which doesn’t have repetition.

The algorithm you write must not use any extra space and should perform with O(n).

Example:

If you are given a string like this,

abcdbbnjkuiokklmnuuurstnvwabcd

to find the longest substring without repetition, you should ignore repetitions in each substring. but must still consider the repeated string to be part of the next substring!!

bb (or) abcdb – is a invalid substring

But, bnjkuio – is a valid substring

Solution

char* longest_substring(char* str)

{

    char* istr = str;

    int checker=0;

    int countmax = 0;

    int maxl = 0;

    char* maxidx = str;

    while(*str != '\0')

    {

        if((checker & (1 << *str)))

        {

            if(maxl < countmax) {

                maxl=countmax;

                maxidx= str; 

            }

            checker=0;

            countmax=1; // include count of the duplicate

        }

        else {

            ++countmax;

        }

        checker |= (1 << *str);

        str++;

    }

    if(maxl < countmax) {

        maxl = countmax;

        maxidx = str;

    }

    char* start = maxidx-maxl;

    if(maxl != 0)     start[maxl] = '\0';

    return start;

}

void main()

{

    char* test = strdup("abcdbbnjkuiokklmnuuurstnvwabcd");

    char* str = longest_substring(test);

}

• In the above code, we just keep track of the max length of the currently found substring in maxl. We also maintain the maxidx (pointer address)
• We just track the max only when you get repetitions in the substring found till now
• checker bit variable helps us in detecting the duplicate in a substring. We set it back to 0 when we are done with detecting duplicate in the first substring.
• after everything is done, we just subtract the maxidx with the substring length to get the start of the substring. Just place a NULL character in maxl location to get the perfect longest substring
• NOTE that, the input string is destroyed!!.. It doesn’t use extra space either for replicating the string argument or for finding duplicates within the string.
• We do traversal only once the whole string and the 2 condition checks gives O(2n) performance. All other operations would be negligibly constant.
• If there is a case like,
• abcdefghijkklmnopqrstu
• What will be the output of the code? If there are equal sized substrings, the function just gives the first found substring!!

Reverse only the words in string

 

Introduction

   Another popular interview question is, reverse the words in the string. We have seen how to do string reverse, simply by swapping the last character with first. But when it comes to reversing just words in the sentence, we should be careful as we also need to do this in-place. When you do in-place reverse of just words, you might need to move the letter further in the string which is unnecessary and confusing.

Approach

  Easy approach is to reverse the whole string using string reverse and then reverse each word one-by-one. I wanted to solve a Google code jam practice problem as well parallel

http://code.google.com/codejam/contest/dashboard?c=351101#s=p1

The above problem requires reversing the words in the strings given as input.

Example:

Input: this is  a test

Output: test a is this

How would do this?

Just string reverse the whole string and then reverse each word one-by-one

Intermediate: tset a si siht

Reverse each word: test a is this

Code

char* str_rev_words(char* str)

{

    char* result = str;

    while(*str != '\0') {

        char* tstr = str;

        char* istr = tstr; // string start

        while(1) {

            if(*(tstr+1) == ' ' || *(tstr+1) == '\0') break;

            tstr++;            

        }

        char* estr = tstr; // string end

        while(!(istr >= estr))

        {

            char tmp = *istr;

            *istr = *estr;

            *estr = tmp;

            istr++;

            estr--;

        }

        if(*(tstr+1) == '\0')

            str = tstr+1;

        else

            str = tstr+2;

    }

    return result;

}

#include <fstream>

using namespace std;

void main()

{

    char line[1000];

    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\B-large-practice.in");

    ofstream outfile ("C:\\Works\\cppassignments\\algorithms\\result.txt");

    myfile.getline(line, 1000);

    int num_of_cases = atoi(line);

    for(int i=1; i<=num_of_cases; i++)

    {

        myfile.getline(line, 1000);

        // doProblem

        str_rev(line);

        outfile<<"Case #"<<i<<": "<<str_rev_words(line)<<endl;

    }

    outfile.close();

    myfile.close();

}

Important points:

• You must note that not just ‘ ‘ is the separator for the word. When you reach the last word, even ‘\0’ will become the separator.
• BUG FIX: When you are reversing the string using swapping last and first, sometimes, first might go beyond than last so, it should be >= condition.

 

Detect Anagram in a String

 

Question

Detect whether a string is anagram of the another string. The normal brute force way would be like this,

Answer

bool detect_anagram(char* src, char* anagram)

{

    int isrc=0, iana=0;

    while(*src != '\0') {

        char* iter = anagram;

        while(*iter != '\0' && *src != ' ') {

            if(*src == *iter) {

                iana++;

                break;

            }

            iter++;

        }

        if(*src != ' ')

            isrc++;

        src++;

    }

    if(iana == isrc)

        return true;

    else

        return false;

}

void main()

{

    char *src=strdup("eleven plus two");

    char *a = strdup("so plew veluent");

    bool st = detect_anagram(src, a);

}

Important points

• The above approach ignores all space character ‘ ‘ and checks for occurrence of a character in the anagram string. If the number of equal characters is equal to the number of characters in source string, then the string is an anagram!!..
• iter is the iterator for the anagram string
• We iterate until we find a matching character in the iter. If we find one, we just increment the count and break.
• iana will be equal to isrc only when characters in source string = anagram string. This is the invariant we need to use to prove the correctness of the above code

Alternate approaches:

• sort both the strings and check whether both are equal!!
• Take count of characters in original string first and then start decrementing the count when seeing the same in the anagram string. If the count becomes zero for all the recorded character entries, then the string is an anagram. This approach is little bit faster than our above O(N2) approach.

String Reverse

 

Question:

    Implement strrev is a possible interview question. How would you do it ?

The simple way is to go to the back of the string, allocate a buffer and push the character from the right to left into the buffer and return it.

But the above approach use extra space

Code:

char* str_rev(char* str)

{

    char* istr = str;

    char* output= (char*) malloc(strlen(str));

    char* ioutput = output;

    while(*str != '\0') {

        str++;

    }

    while(--str != istr) {

        *output = *str;

        output++;

    }

    *output = *str;

    *(output+1) = '\0';

    return ioutput;

}

void main()

{

    char* rstr = str_rev("rajan");

}

 

How would you do without using this extra space?

Just swap the last element in the string with the first element until you reach the middle.

char* str_rev(char* str)

{

    char* tstr = str;

    char* istr = tstr; // string start

    while(*tstr != '\0') tstr++;

    char* estr = --tstr; // string end

    while(istr != estr)

    {

        char tmp = *istr;

        *istr = *estr;

        *estr = tmp;

        istr++;

        estr--;

    }

    return str;

}

void main()

{

    char* ptr = strdup("rajan");

    char* rstr = str_rev(ptr);

}

Important points:

• if char* ptr=”rajan” is used, the above program will crash since, “rajan” is a const literal present part of code segment which cannot be modified.
• strdup creates a new pointer from the input const char*. We use that to remove the const
• free on ptr should be called !!

Is a String rotated or not?

“A Simple word within a word. But little bit tricky if you did not think in normal way.”

Introduction

    A very simple interview question,

You have a string like “simple”

You are given a string “esimpl”. You need to verify whether the given string is just a rotation of the original string.

How will you detect rotations in general terms? We go thru the elements and find the place where the shift happened. From there we start comparing. But that will complicate things for the given problem.

Concept

   The simple way is to just concat the replica of the rotated string:

“esimplesimpl”

When you do concat, you see that, simple is again getting recreated in the buffer. Then to check whether its really a rotation, it becomes so simple, just search for base string “simple” within the concat string.

There is one more condition which reduces the time taken to search inside string, The string Length.

Code

/*

Whether the string is rotated or not?

simple

plesim

*/

bool isRotated(char* input, char* rotated)

{

    if(strlen(input) != strlen(rotated))

        return false;

    char* buff = (char*) malloc(strlen(rotated)*2);

    strcat(buff, rotated);

    strcat(buff, rotated);

    char* pos = strstr(buff, input);

    if(pos != NULL)

        return true;

    else

        return false;

}

void main()

{

    bool test = isRotated("simple", "esimpl");

}

Important points:

• This is the simplest code and it is self understandable
• The only place where this is useful is in a spell checker application :)
• Just try “esimple” in a winword document, spell checker will detect that as an error and gives you a matching suggestion from the dictionary. :)