Handshakes question
September 4, 2012
Print character occurring maximum number of times in a string
September 8, 2012

Longest substring of unique characters

Given a String in which characters may be repeating. Find the length of longest substring of where all characters are unique (non-repeating).

For Example: If the String is "RITAMBHARA"
Length of Longest substring with unique characters = 7 ("RITAMBH")

Solution:

Since we only need to find length of the substring (and not the unique substring itself). We can have two variables for:
1. Length of longest unique substring encountered till now. Lets call it maxLen.
2. Length of unique substring including the current character. Lets call it currentLen

We also need hash array which holds the position (within the string) where a particular character was last seen. Lets call this array lastSeen.

Algorithm:

1. Set all elements of lastSeen to -1 (Not seen till now)
    maxLen = 0;
    currentLen = 0;
2. For each character (ch) in String
    IF(lastSeen[ch] == -1)    // Character Not seen till now
        currentLen++
    ELSE IF lastSeen[ch] is not part of current Lap
        currentLen++
    ELSE
        update currentLen to be after the lastSeen[ch].
    IF currentLen > maxLen
        maxLen = currentLen

Code:

int longestUniqueSubstring(char *str)
{
    if(str == NULL)
        return -1;
    int currentLen = 0;
    int maxLen = 0;
    int lastSeen[256];
    for(int i=0; i<256; i++)
        lastSeen[i] = -1;
    int n = strlen(str);
    for (int i = 0; i < n; i++)
    {
        // If character is not present in the current lap
        if (lastSeen[str[i]] == -1 || i - currentLen > lastSeen[str[i]])
        {
            currentLen++;
        }
        else
        {
            if (currentLen > maxLen)
                maxLen = currentLen;
            currentLen = i - lastSeen[str[i]];
        }
        // Updating Last Seen for current character
        lastSeen[str[i]] = i;
    }
    // In case the longest substring is at end
    if (currentLen > maxLen)
        maxLen = currentLen;
    return maxLen;
}

Time Complexity: O(n)
Extra Space Required: O(d) (Where d is the total number of possible characters – 256 for English)

1 Comment

  1. Muhammad Tahir says:

    I want to change this code according to my excercise
    what is the longest substring of characters strictly rising (the following is greater (>) of the previous)for example abcdghijabcdefghij so strictly rising is abcdefghij
    what is the longest substring of successive characters (i.e.: fhkjshdfruytyzABCDEfglsj => 7) ABCDEfgl
    please someone reply me with changes
    #include
    #include
    #include
    #include
    #include
    main(){
    int longestUniqueSubstring(char *str)
    {
    if(str == NULL)
    return -1;
    int currentLen = 0;
    int maxLen = 0;
    int lastSeen[256];
    for(int i=0; i<256; i++)
    lastSeen[i] = -1;
    int n = strlen(str);
    for (int i = 0; i lastSeen[str[i]])
    {
    currentLen++;
    }
    else
    {
    if (currentLen > maxLen)
    maxLen = currentLen;
    currentLen = i – lastSeen[str[i]];
    }
    // Updating Last Seen for current character
    lastSeen[str[i]] = i;
    }
    // In case the longest substring is at end
    if (currentLen > maxLen)
    maxLen = currentLen;
    return maxLen;
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *