leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }


/**
 * Solution (DP, O(n)):
 *
 * Assume L[i] = s[m...i], denotes the longest substring without repeating
 * characters that ends up at s[i], and we keep a hashmap for every
 * characters between m ... i, while storing <character, index> in the
 * hashmap.
 * We know that each character will appear only once.
 * Then to find s[i+1]:
 * 1) if s[i+1] does not appear in hashmap
 *    we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]
 * 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k
 *    let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
 *    entry in hashmap to mark the latest occurency of s[i+1].
 *
 * Since we scan the string for only once, and the 'm' will also move from
 * beginning to end for at most once. Overall complexity is O(n).
 *
 * If characters are all in ASCII, we could use array to mimic hashmap.
 */

int lengthOfLongestSubstring(string s) {
    // for ASCII char sequence, use this as a hashmap
    vector<int> charIndex(256, -1);
    int longest = 0, m = 0;

    for (int i = 0; i < s.length(); i++) {
        m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case
        charIndex[s[i]] = i;
        longest = max(longest, i - m + 1);
    }

    return longest;
}

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}

        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength

// testlongsetString.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include<iostream>

using namespace std;

void GetMaxUnRepeatSubStr(char *str)
{
	//global var
	int hashTable[256] ={0};
	char* pMS = str;
	int mLen = 0;

	//temp var
	char* pStart = pMS;
	int len = mLen;
	char* p = pStart;
	while(*p != '\0')
	{
		if(hashTable[*p] == 1)
		{
			if(len > mLen)
			{
				pMS = pStart;
				mLen = len;
			}

			while(*pStart != *p)
			{
				hashTable[*pStart] = 0;
				pStart++;
				len--;
			}
			pStart++;
		}
		else
		{
			hashTable[*p] = 1;
			len++;
		}
		p++;
	}
	// check the last time
	if(len > mLen)
	{
		pMS = pStart;
		mLen = len;
	}
	//print the longest substring
	while(mLen>0)
	{
		cout<<*pMS<<" ";
		mLen--;
		pMS++;
	}
	cout<<endl;
}

int main()
{
	char* str1="bdabcdcf";
	GetMaxUnRepeatSubStr(str1);
	char* str2="abcdefb";
	GetMaxUnRepeatSubStr(str2);
	char* str3="abcbef";
	GetMaxUnRepeatSubStr(str3);

	return 0;
}