给出一个字符串，只包含A，B，C三种字符，现在需要找到一个最长的子串，包含A，B，C的个数一样多。返回这样的最长子串的长度。
1. 两层遍历
这个方法比较好想，既然我们是要找到一个子串，我们可以枚举这个子串的开头位置。对于任何一个开头，我们往后找可能的末尾位置。遍历的同时使用变量记录各个字符的个数，然后检查字符出现的个数是否一样。记录下最长的满足条件的字符串长度即可。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class LongestSubStrContainsEquABC {
public static int maxLen(String s) {
int len;
if(s == null || (len = s.length()) < 3) return 0;
int ans = 0, a = 0, b = 0, c = 0, i = 0, j;
char cc;
for(; i < len; ++i) {
a = 0;
b = 0;
c = 0;
for(j = i; j < len; ++j) {
cc = s.charAt(j);
if(cc == 'A') ++a;
else if(cc == 'B') ++b;
else ++c;
if(a == b && a == c) ans = Math.max(ans, j - i + 1);
}
}
return ans;
}
}
|
2. 使用哈希表
如果理解平移操作，就很容易理解这个方法。对于一个图形进行平移后，图形所有对应点之间的距离是相等的，如下图所示：
我们不妨把字符A，B，C出现的次数放在条形图中，记录条形图顶端形成的形状。如下图所示：
我们可以遍历字符串，统计字符ABC出现的次数，在统计的同时，我们需要查看在之前的哪一步出现了统计图顶端的图形。假设当我们遍历到第$j$个字符的时候，发现相同的图形出现在遍历第$i$个字符的时候，那么我们可以知道从$i+1$到$j$这一段子串包含的ABC字符个数必然相同。那么我们怎么记录统计图顶端形成的图形呢？其实这个图形的本质就是ABC各个字符出现次数的差异，我们只需要记录下差异，就相当于记录下了图形。我们在遍历的时候，用哈希表记录下遍历到每一步的时候，此时统计图形成的图形，以便后续遍历的时候查找。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import java.util.HashMap;
public class LongestSubStrContainsEquABC2 {
public static int maxLen(String s) {
int len;
if(s == null || (len = s.length()) < 3) return 0;
HashMap<String, Integer> diffShapeMap = new HashMap<>();
diffShapeMap.put("0-0", -1);
int a = 0, b = 0, c = 0, ans = 0;
char cc;
for(int i = 0; i < len; ++i) {
cc = s.charAt(i);
if(cc == 'A') ++a;
else if(cc == 'B') ++b;
else ++c;
String diffShape = (b - a) + "-" + (c - b);
if(diffShapeMap.containsKey(diffShape)) ans = Math.max(ans, i - diffShapeMap.get(diffShape));
else diffShapeMap.put(diffShape, i);
}
return ans;
}
}
|
