Leetcode——最长不重复子串

题：从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度并输出一条最长不重复子串。

自己的第一反应是使用动态规划来解决这个问题。在搜集资料之后，发现共有三种解决方案：

1. 使用hash

2. 使用DP + Hash

==================================================================

基本方法，使用简单Hash

其实判断重复问题最应该想到的是Hash，建立一个简单的hash table，key为字符的ASCII码值，value为该字符是否已经在当前子串中出现过（出现过为1，未出现为0）。最简单的方法就是对所有的子串进行查重，复杂度为θ(n^2)。

在扫描过程中，我们需要找到尽可能长的不重复子串，我称之为“极长不重复子串”。假设s[i...j]的当前的极长不重复子串为L(i,j)，那么L(i, j+1)的长度分为两种情况：

    1. 上一个s[j+1]代表的字符出现在L(i.j)的起始位置之前，那么s[j+1]应该被添加到当前极长不重复子串中；

    2. 上一个s[j+1]代表的字符出现在L(i,j)的起始位置之后，那么记录下L(i,j)，开始跟踪新的极长不重复子串。

在扫描完所有的str[0...n]，str[1...n]，str[2...n]....后，最长的极长字符串就是字长不重复子串

源代码为：

/* 最长不重复子串 设串不超过30
 * 我们记为 LNRS
 */
int maxlen;
int maxindex;
void output(char * arr);
 
/* LNRS 基本算法 hash */
char visit[256];
 
void LNRS_hash(char * arr, int size)
{
    int i, j;
    for(i = 0; i < size; ++i)
    {
        memset(visit,0,sizeof visit);
        visit[arr[i]] = 1;
        for(j = i+1; j < size; ++j)
        {
            if(visit[arr[j]] == 0)
            {
                visit[arr[j]] = 1;
            }else
            {
                if(j-i > maxlen)
                {
                    maxlen = j - i;
                    maxindex = i;
                }
                break;
            }
        }
        if((j == size) && (j-i > maxlen))
        {
            maxlen = j - i;
            maxindex = i;
        }
    }
    output(arr);
}

=========================================================================

使用DP+hash。使用DP以空间换时间的方法来解决此问题，DP最重要的思想就是要记录。

在第一种方法当中，我们扫面了所有的子串。但是如果str1是str2的子串，那么str1的最长不重复子串肯定小于或者等于str2。我们可以直接扫描整个给定的字符串，并在扫描过程中记录下所有扫描到极大字符串，找到最长的即可（仿照人工的思路）。

使用hash表来保存一个字符最近被扫描的时候所处的位置

代码如下：

class Solution 
{
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;

		int visit[256];		//用来保存最近扫描到一个字符的位置
		int max_length;		//目前最大不重复子串的长度
		int start_index;	//目前最大不重复子串的起始索引
		int last_start;		//目前扫描的极大不重复子串的起始索引
		int last_length;	//目前扫描的极大不重复子串的长度

		start_index = 0;
		max_length = 0;
		last_start = 0;
		memset(visit, -1, sizeof(int) * 256);

		//第一个字符
		visit[s[0]] = 0;
		last_length = 1;

		for (int i = 1; i < s.size(); i++)
		{
			if (visit[s[i]] == -1)
			{
				last_length++;
				visit[s[i]] = i;
			}
			else if (visit[s[i]] < last_start)
			{
				last_length++;
				visit[s[i]] = i;
			}
			else
			{
				if (last_length > max_length)
				{
					max_length = last_length;
					start_index = last_start;
					last_start = visit[s[i]] + 1;		//更新当前极长子串的起点，是重复字符的后一位
					last_length = i - last_start + 1;
					visit[s[i]] = i;
				}
				else
				{
					last_start = visit[s[i]] + 1;
					last_length = i - last_start + 1;
					visit[s[i]] = i;
				}
			}
		}

		if (last_length > max_length)
		{
			max_length = last_length;
		}
		return max_length;
	}
};