在字符串中找到最长连续字符的高效方法

Question

这段代码可以正常运行，但我正在寻找一种优化方法。如果你查看长字符串，你会发现 'l' 连续出现了五次。没有其他字符连续出现这么多次。因此，输出结果为5。现在的问题是这种方法检查每个字符，即使找到最大值后，它仍会继续检查其余字符。有更有效率的方法吗？

public class Main {
    public static void main(String[] args) {
        System.out.println(longestStreak("KDDiiigllllldddfnnlleeezzeddd"));
    }
    private static int longestStreak(String str) {
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            int count = 0;
            for (int j = i; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    count++;
                } else break;
            }
            if (count > max) max = count;
        }
        return max;
    }
}

- EsAMe

---

我认为这可能更适合在https://codereview.stackexchange.com上。 - azurefrog

好的，当您当前的最大值超过剩余字符数时(max > str.length()-i)，您可以停止。 - Arnaud

@Arnaud，这仍然不是最优解决方案。请查看下面的答案，以获取O（N）复杂度的最佳解决方案。 - Damian-Teodor Beleș

Answer 1

我们可以在单次迭代中添加前一个字符计数的变量。另外，作为额外的优化，如果i + max - currentLenght < str.length()，我们将停止迭代。这意味着max不能改变。

private static int longestStreak(String str) {
    int maxLenght = 0;
    int currentLenght = 1;
    char prev = str.charAt(0);
    for (int index = 1; index < str.length() && isMaxCanBeChanged(str, maxLenght, currentLenght, index); index++) {
        char currentChar = str.charAt(index);
        if (currentChar == prev) {
            currentLenght++;
        } else {
            maxLenght = Math.max(maxLenght, currentLenght);
            currentLenght = 1;
        }
        prev = currentChar;
    }
    return Math.max(maxLenght, currentLenght);
}

private static boolean isMaxCanBeChanged(String str, int max, int currentLenght, int index) {
    return index + max - currentLenght < str.length();
}

- i.bondarenko

---

我该如何计算它相对于其他方法的效率？@i.bondarenko - Pie

就时间复杂度而言，它是线性O(n)。它可能与其他一些算法相等。但正如我们所看到的，我添加了一个优化，在某些情况下它更有效率。例如，如果您有一个带有非常长连续字符串的大字符串，在这种情况下，您可以比其他算法更早地停止迭代（请参见isMaxCanBeChanged(...)中的条件）。 - i.bondarenko

有其他量化衡量效率的方法，例如返回一个数字表示它执行所需的时间（x毫秒）。@i.bondarenko - Pie

算法花费的毫秒数非常依赖于计算机配置。我们可以在同一台计算机上运行一些测试并比较不同的算法，但我没有这样的测试数据集，它真的取决于测试数据集。 - i.bondarenko

Answer 2

是的，有的。C++ 代码：

string str = "KDDiiigllllldddfnnlleeezzeddd";
int longest_streak = 1, current_streak = 1; char longest_letter = str[0];
for (int i = 1; i < str.size(); ++i) {
    if (str[i] == str[i - 1])
        current_streak++;
    else current_streak = 1;
    if (current_streak > longest_streak) {
        longest_streak = current_streak;
        longest_letter = str[i];
    }
}
cout << "The longest streak is: " << longest_streak << " and the character is: " << longest_letter << "\n";

如果需要，我可以提供Java代码，但我认为你已经明白了。

public class Main {
    public static void main(String[] args) {
        System.out.println(longestStreak("KDDiiigllllldddfnnlleeezzeddd"));
    }
    private static int longestStreak(String str) {
        int longest_streak = 1, current_streak = 1; char longest_letter = str.charAt(0);
        for (int i = 1; i < str.length(); ++i) {
            if (str.charAt(i) == str.charAt(i - 1))
                current_streak++;
            else current_streak = 1;
            if (current_streak > longest_streak) {
                longest_streak = current_streak;
                longest_letter = str.charAt(i);
            }
        }
        return longest_streak;
    }
}

- Damian-Teodor Beleș

---

你能把这段代码转换成Java吗？因为我不知道C++怎么用。 - EsAMe

@EsAMe 提供的代码非常类似于Java。 - Tim Biegeleisen

最好你这样做，这样我比较起来会更容易。 - EsAMe

完成，现在请检查。 - Damian-Teodor Beleș

@EsAMe 请接受帮助过你的答案。接受答案不仅可以方便地找到答案，还会提高你的声誉。 - Yoshikage Kira

Answer 3

这里有一个正则表达式的魔法解决方案，虽然可能有点粗暴，但还是很厉害的。我们可以从原始输入的字符数开始迭代，每次减少一个字符，尝试用正则表达式替换该长度的连续字符。如果替换成功，那么我们就知道找到了最长的连续字符。

String input = "KDDiiigllllldddfnnlleeezzeddd";
for (int i=input.length(); i > 0; --i) {
    String replace = input.replaceAll(".*?(.)(\\1{" + (i-1) + "}).*", "$1");
    if (replace.length() != input.length()) {
        System.out.println("longest streak is: " + replace);
    }
}

这将打印：

longest streak is: lllll

- Tim Biegeleisen

Answer 4

循环可以被重写得更小一些，但主要是条件可以被优化：

i < str.length() - max

- Joop Eggen

Answer 5

使用Stream和Collector。它应该返回所有最高重复元素。

代码：

String lineString = "KDDiiiiiiigllllldddfnnlleeezzeddd";
String[] lineSplit = lineString.split("");
Map<String, Integer> collect = Arrays.stream(lineSplit)
.collect(Collectors.groupingBy(Function.identity(), Collectors.summingInt(e -> 1)));
int maxValueInMap = (Collections.max(collect.values()));
for (Entry<String, Integer> entry : collect.entrySet()) {
   if (entry.getValue() == maxValueInMap) {
      System.out.printf("Character: %s, Repetition: %d\n", entry.getKey(), entry.getValue());
   }
}

输出：

Character: i, Repetition: 7
Character: l, Repetition: 7

注：我不确定这段代码的效率如何，我刚学习了流编程。

- Yoshikage Kira