3773. Maximum Number of Equal Length Runs 🔒

Description

You are given a string s consisting of lowercase English letters.

A run in s is a substring of equal letters that cannot be extended further. For example, the runs in "hello" are "h", "e", "ll", and "o".

You can select runs that have the same length in s.

Return an integer denoting the maximum number of runs you can select in s.

Example 1:

Input: s = "hello"

Output: 3

Explanation:

The runs in s are "h", "e", "ll", and "o". You can select "h", "e", and "o" because they have the same length 1.

Example 2:

Input: s = "aaabaaa"

Output: 2

Explanation:

The runs in s are "aaa", "b", and "aaa". You can select "aaa" and "aaa" because they have the same length 3.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters only.

Solutions

Solution 1: Hash Table

Thinking

We may keep only runs of one common length, so the answer is the most frequent run length. One groupby pass counts lengths and we take the maximum frequency.

We can use a hash table \(\textit{cnt}\) to record the number of occurrences of each run length. We traverse the string \(s\), and for each run, we calculate its length \(m\) and increment \(\textit{cnt}[m]\) by \(1\). Finally, the answer is the maximum value in \(\textit{cnt}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the string \(s\).

Python3JavaC++GoTypeScript

class Solution:
    def maxSameLengthRuns(self, s: str) -> int:
        cnt = Counter()
        for _, g in groupby(s):
            cnt[len(list(g))] += 1
        return max(cnt.values())

class Solution {
    public int maxSameLengthRuns(String s) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                ++j;
            }
            int m = j - i;
            ans = Math.max(ans, cnt.merge(m, 1, Integer::sum));
            i = j;
        }
        return ans;
    }
}

class Solution {
public:
    int maxSameLengthRuns(string s) {
        unordered_map<int, int> cnt;
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s[j] == s[i]) {
                ++j;
            }
            int m = j - i;
            ans = max(ans, ++cnt[m]);
            i = j;
        }
        return ans;
    }
};

func maxSameLengthRuns(s string) (ans int) {
    cnt := map[int]int{}
    n := len(s)
    for i := 0; i < n; {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        m := j - i
        cnt[m]++
        ans = max(ans, cnt[m])
        i = j
    }
    return
}

function maxSameLengthRuns(s: string): number {
    const cnt: Record<number, number> = {};
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < n;) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            ++j;
        }
        const m = j - i;
        cnt[m] = (cnt[m] || 0) + 1;
        ans = Math.max(ans, cnt[m]);
        i = j;
    }
    return ans;
}

3773. Maximum Number of Equal Length Runs 🔒

Description

Solutions

Solution 1: Hash Table

Comments