LeetCode 1624. 两个相同字符之间的最长子字符串

思路

空间换时间，存了3个26位的数组，temp[26]记录每个字符目前为止最大的间隔。
1

(这一道题一直被我错误地理解成 子字符串中不能够出现两端的相同字符，导致运行时错了无数次还在凌乱…)

解答

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) 
    {
       vector<int> oldA(26,-1); 
       vector<int> newA(26,0);
       vector<int> temp(26,0); 
       for(int i = 0; i < s.length(); ++i)
       {
            if(oldA[s[i]-'a'] != -1 && newA[s[i]-'a'] != 0)
            {   
                oldA[s[i]-'a'] = newA[s[i]-'a'];
                newA[s[i]-'a'] = i;
            }
            else if (oldA[s[i]-'a'] != -1 && newA[s[i]-'a'] == 0)
                newA[s[i]-'a'] = i;
            else 
                oldA[s[i]-'a'] = i;
            if(( newA[s[i]-'a']- oldA[s[i]-'a'] > temp[s[i]-'a'] )&& ( newA[s[i]-'a']!= 0))
                temp[s[i]-'a'] = newA[s[i]-'a']- oldA[s[i]-'a'];
       }
       for(int i=0;i<26;++i)
       {
           cout<<oldA[i]<<endl;
       }
       return *max_element(temp.begin(),temp.end())-1; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

官方解答

只用了一个数组，还是很妙的
26个字母的initialArray中都存放-1，如果这个字母首次出现，则此字母对应的initialArray中的-1更改为首次出现的地址。然后，这个initialArray里只要此字母对应的不是-1，说明此字母已经出现过了，那么将其现在的位置减去第一次出现的位置减去1，与目前的maxLength做比较即可.

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) 
    {
       vector<int> initialArray(26,-1); 
       int maxLength = -1;
       for(int i = 0; i < s.length();++i)
       {
            if(initialArray[s[i]-'a'] == -1)
            {   
                initialArray[s[i]-'a'] = i;
            }
            else 
                maxLength = max(maxLength, i-initialArray[s[i]-'a']-1);
       }
       return maxLength;
       
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19