Skip to content

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 <= 105
  • s consists of lowercase English letters only.

Solutions

Solution 1: Hash Table

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\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments