面试题48:最长不含重复字符的子字符串

题目

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含‘a’~‘z’的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度为4.

解题思路

1. 定义函数curlength表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。
2. 分两种情况:
   (a): 第i个字符之前没出现过，那么curlength++。
   例如:在字符串“arabcacfr”中，显然a没有出现过，r也没有出现过，curlength=2.到目前为止最长的不含重复字符的子字符串为“ar”。
   (b) 若第i个字符之前出现过，那么就要分情况讨论了。
   b.1) 计算第i个字符和它上次出现在字符串中的位置的距离d，若d<=f(i-1)，则第i个字符上次出现在f(i-1)对应的最长子字符串之中，因此f(i)=d。如上例中计算f(2)，即以下标为2的字符‘a’为结尾的不含重复字符的子字符串的最长长度。因为字符‘a’在之前出现过，该字符上次出现在下标为0的位置，距离d=2<=f(1)=2，也就是说字符‘a’出现在f(1)对应的最长不含重复字符的子字符串“ar”中，此时f(2)=d，即f(2)=2，对应的最长不含重复字符的字符串是“ra”
   b.2) 若d>f(i-1)，此时第i个字符上次出现在f(i-1)对应的最长子字符串之前，因此仍然有f(i)=f(i-1)+1。如上例中的字符“r”，即f(8)。以它前一个字符‘f’为结尾的最长不含重复字符的子字符串“acf”，f(7)=3。发现“r”在下标为1的时候出现过，这两次出现的距离d=7>f(7)。说明上一个字符“r”不在f(7)对应的最长不含重复字符的子字符串“acf”中，就可以直接把“r”拼接到“acf”后面，因此f(8)=f(7)+1,即f(8)=4,对应最长不含重复字符的子字符串“acfr”。

代码

• 用map容器存放字符和其出现的位置，即map[str[i]]=i，发现若后面重复出现某字符，则字符所在位置会实时变化。

1. 比如字符“a”，会从map[str[0]]=0-->map[str[2]]=2-->map[str[5]]=5。
2. 第i个字符和它上次出现在字符串中的位置的距离d用i-map[str[i]]表示。
3. 若字符未出现过，则curLength递增，若出现过则判断距离。
   在前一个最长的子字符串出现过，则比较当前最长值curLength和maxLength，取最大值，并更新当前最长值curLength；若该字符未在前一个最长字符串出现过，则当前最长值递增。

class Solution{
    public:
        int lengthOfLongestSubstring(string s)
        {
            if(s.empty())
            {
                return 0;
            }
            map<char ,int> mp;
            int maxLength = 0;//最长不含重复字符的字符串长度
            int curLength = 0;//当前不含重复字符的字符串长度

            for(int i = 0;i< s.size();i++)
            {   //第i个字符之前没有出现过
                if(mp.find(s[i]) == mp.end())
                { //map.find()查找关键字key是否存在，若存在则返回
                  //该键的元素的迭代器，若不存则返回map.end()
                    curLength++;
                }
                //第i个字符之前出现过
                else if(i-mp[s[i]] <= curLength)
                {
                    maxLength = maxLength > curLength ? maxLength:curLength;
                    curLength = i - mp[s[i]];
                }
                else
                {
                    curLength++;
                }
                mp[s[i]] = i;
                maxLength = maxLength > curLength?maxLength:curLength;
            }
            return maxLength;
        }
}

• 书上的方式

1. 创建一个数组来存放每个字符上次出现在字符串中位置的下标。该数组所有元素的值都初始化为-1，负数表示该元素对应的字符在字符串中没有出现过，若出现则把该字符在字符串中的位置存储到数组对应的元素中。
2. 用i-prevIndex表示第i个字符和它上次出现在字符串中的位置的距离d。用curLength表示f(i)的值。
3. 两种情况下，子字符串的长度递增。一种情况:字符从未出现过，另一种情况:距离d>前一个子字符串的长度。

class Solution{
    public:
        int longestSubstringWithoutDuplication(string s)
        {
            int curLength = 0;
            int maxLength = 0;

            int* position = new int[26];
            for(int i = 0;i<26;++i)
            {
                position[i] = -1;
            }
            for(int i=0;i<s.length();++i)
            {
                int prevIndex = position[s[i]- 'a'];
                if(prevIndex < 0 || i-prevIndex > curLength)
                {
                    ++curLength;
                }
                else
                {
                    if(curLength > maxLength)
                    {
                        maxLength = curLength;
                    }
                    curLength = i-prevIndex;
                }
                position[s[i]-'a'] = i;
            }
            if(curLength > maxLength)
            {
                maxLength = curLength;
            }
            delete[] position;
            return maxLength;
        }

};

完整代码见GitHub