Count Group Occurrences

Problem Overview

A group is a maximal run of one letter, so aaabbcca has four groups: aaa, bb, cc, and a.

Intuition

A group is a maximal run of one letter, so aaabbcca has four groups: aaa, bb, cc, and a. The task is to count how many distinct letters form exactly k such groups. Scanning the string once is enough. At the start of every run, raise a counter for that letter in a 26 slot array. Letters that never appear stay at zero. After the scan, count how many slots equal k. The length of a run does not matter, only that the run began. Jumping through equal characters keeps each group charged once. Every character of the string must be read, so the linear pass is already the tight bound.

Algorithm

1Allocate a counter of length 26 for the lowercase letters.
2Walk the string by runs. At the first character of a run, raise that letter's counter, then skip the rest of the run.
3Scan the 26 counters and add one to the answer for every value that equals k.
4Return that answer.

Example Walkthrough

Input: s = "geeksforgeeks", k = 2

1. The runs include g, ee, k, s, f, o, r, g, ee, k, s.
2. Letters g, e, k, and s each start exactly two runs. The others start one.
3. Four letters match k equals 2, so the answer is 4.

Output: 4

Common Pitfalls

• Count groups, not raw character frequency. The string aaaaa is one group of a, even though a appears five times.
• A letter that returns after a different letter starts a new group. In aaabbcca the final a is a second group for a.
• Only letters whose group count equals k are kept. A letter with more groups than k does not count.
• The alphabet size is fixed at 26, so the counter uses constant extra space.

Count Group Occurrences.java

Java

// Approach: A group is a maximal run of the same letter. Walk the string once
// and raise a 26-slot counter at the start of every run. Then count how many
// letters have a run total of exactly k. Every character must be read, so the
// linear scan is already tight.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    int getCount(String s, int k) {
        int[] cnt = new int[26];
        int n = s.length();

        for (int i = 0; i < n; ) {
            char c = s.charAt(i);
            cnt[c - 'a']++;
            while (i < n && s.charAt(i) == c) {
                i++;
            }
        }

        int ans = 0;
        for (int c : cnt) {
            if (c == k) {
                ans++;
            }
        }
        return ans;
    }
}

Was this solution helpful?