Saturday, March 28, 2015

LeetCode OJ - Longest Substring Without Repeating Characters

Problem:

Please find the problem here.

Solution:

This is similar to the maximum contiguous sum problem, in the sense that we are trying to find a best sub-string. We will use a similar approach to keep track of the best sub-string we have seen so far and the best sub-string that ends with the last character.

Assume we already have the two best sub-strings for a prefix, now we extend that prefix for one more character. Ideally we would want to extend the best sub-string that ends with that character, but if such character occurs within the last best sub-string that ends with the last character, we have no choice but to trim it, the overall best sub-string would then just be the best of both.

It is rather clumsy to read that explanation in words, let see it in an example, let say, we are doing this string

A B C A P P

Initially, the best sub-string is 'A' and the best sub-string that ends with the last character is also 'A', we will tabulate it as follow

Prefix
Best Sub-string
Best Sub-String ends at last character
A
A
A
AB
AB
AB
ABC
ABC
ABC
ABCA
ABC
BCA (Now we cannot extend, so trimmed)
ABCAP
BCAP (BCAP is better than ABC)
BCAP
ABCAPP
BCAP
P (We have really no choice here)

I hope that is clear how it works, in order to quickly determine whether or not we need trimming, I have a map to quickly look-up the last index of a certain character.

Also note that the best sub-string is not always unique. ABCAB, for example, have ABC, BCA and CAB all are best sub-strings. That is probably why the question ask only for the length of it, for that must be unique.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/longest-substring-without-repeating-characters/

#include "LEET_LONGEST_SUBSTRING_WITHOUT_REPEATING_CHARACTERS.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

// #define LOG

namespace _LEET_LONGEST_SUBSTRING_WITHOUT_REPEATING_CHARACTERS
{
    class Solution 
    {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            if (s.length() == 0)
            {
                return 0;
            }
            else
            {
                int best_s = 0;
                int best_e = 0;
                int best_l = 1;
                int last_s = 0;
                int last_e = 0;
                int last_l = 1;
                map<char, int> last_index;
                last_index.insert(pair<char, int>(s[0], 0));

                for (unsigned int i = 1; i < s.length(); i++)
                {
                    map<char, int>::iterator probe = last_index.find(s[i]);
                    if (probe == last_index.end())
                    {
                        // the current character is not found - so simply extend the last sequence
                        last_index.insert(pair<char, int>(s[i], i));
                    }
                    else
                    {
                        int last_character_index = probe->second;
                        probe->second = i;
                        if (last_character_index >= last_s)
                        {
                            last_s = last_character_index + 1;
                        }
                        else
                        {
                            // There is an occurrence of the current character, but that doesn't matter since it was out already
                        }
                    }
                    last_e = i;
                    last_l = last_e - last_s + 1;
                    if (last_l > best_l)
                    {
                        best_l = last_l;
                        best_s = last_s;
                        best_e = last_e;
                    }
                    

#ifdef LOG
                    cout << "Current string: ";
                    for (unsigned int j = 0; j <= i; j++)
                    {
                        cout << s[j];
                    }
                    cout << endl;

                    cout << "The best string: ";
                    for (int bi = best_s; bi <= best_e; bi++)
                    {
                        cout << s[bi];
                    }
                    cout << endl;

                    cout << "The last string: ";
                    for (int li = last_s; li <= last_e; li++)
                    {
                        cout << s[li];
                    }
                    cout << endl;
                    cout << endl;
#endif
                }

                return best_l;
            }
        }
    };
};

using namespace _LEET_LONGEST_SUBSTRING_WITHOUT_REPEATING_CHARACTERS;

int LEET_LONGEST_SUBSTRING_WITHOUT_REPEATING_CHARACTERS()
{
    Solution solution;
    cout << solution.lengthOfLongestSubstring("abcabcbb") << endl;
    cout << solution.lengthOfLongestSubstring("bbbbb") << endl;
    return 0;
}

No comments :

Post a Comment