找出没有连续重复字符的最长子串长度

Question

在最近的一次面试中，我被问到如何找出最长的子字符串，要求里面不能有连续重复的字符。这和我们通常问的问题有点不同，因为它只关注连续重复的字符。

举个例子：

WOOD : 2

Italics : 7

当然，这个问题必须在 O(N) 的时间和空间内解决。

Answer 1

希望下面的代码能对你有帮助。谢谢。

import java.util.HashSet;

public class SubString {
    public static String subString(String input){

        HashSet<Character> set = new HashSet<Character>();

        String longestOverAll = "";
        String longestTillNow = "";

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (set.contains(c)) {
                longestTillNow = "";
                set.clear();
            }
            longestTillNow += c;
            set.add(c);
            if (longestTillNow.length() > longestOverAll.length()) {
                longestOverAll = longestTillNow;
            }
        }

        return longestOverAll;
    }

    public static void main(String[] args) {
        String input = "kaveeshkanwal abcvdghytrqp";//"substringfindout";
        System.out.println(subString(input));
    }
}

Answer 2

---

public static void main(String[] args){
    String s = "italics";
    char[] c = s.toCharArray();
    int tmp = 1;
    for (int i = 1; i < s.length(); i++) {
        if (c[i] == c[i-1]){
            tmp = 0;
            continue;
        }
        tmp++;
    }
    System.out.println(tmp);
}

输出的结果是1

有一个字符串s，它的内容是"italics"

然后输出的结果变成了7

Answer 3

在Python中，我会这样处理：

def interview(s):
    current = longest = 0
    for index, char in enumerate(s):
        if index and char == s[index - 1]:
            longest, current = max(longest, current), 0
        current += 1
    return max(longest, current)

Answer 4

逐个字符地查看这个字符串。要记录你已经前进了多少个字符，而没有遇到重复的字符，可以用一个变量，比如叫“repeatcounter”。如果下一个字符和当前字符相同，就把这个计数器的值记录到另一个变量里（只有当这个值比之前的值大时才记录），然后把“repeatcounter”重置为0。