Most Frequent N-Gram

Write a function that takes a string s and an integer n, and returns the most frequent n-gram (substring of length n). If there's a tie, return the first one encountered.

Examples:

mostFrequentNGram("abcdabxe", 2) → "ab"
  "ab" appears twice; everything else appears once.
mostFrequentNGram("banana", 2) → "an"
  Substrings: "ba", "an", "na", "an", "na"
  "an" and "na" both appear twice, but "an" is encountered first.
mostFrequentNGram("aaaa", 1) → "a"
mostFrequentNGram("abcdef", 3) → "abc"
  All trigrams appear once; return the first.

Constraints:

• 1 ≤ n ≤ s.length()
• s contains only lowercase English letters

How do we approach this problem?

We need to examine every substring of length n and count its occurrences. A sliding window of fixed size n is the natural fit — slide across the string, extract each window, and track frequencies in a map.

For problems like this, there’s a general fixed-size sliding window template worth internalizing:

Map<String, Integer> freq = new HashMap<>();

for (int left = 0, right = 0; right < s.length(); right++) {
    // 1. EXPAND: add right element to your state
    // 2. When window hits target size:
    if (right - left + 1 == k) {
        // 3. RECORD: process this window
        // 4. SLIDE: remove left element, advance left
        left++;
    }
}

In many sliding window problems, you maintain running state during the EXPAND step — character frequency maps, running sums, and so on. This problem is a simplified case: we don’t need incremental state. When the window reaches size n, we just extract the substring directly and count it. That makes it a great first problem to practice the template on before tackling variants that require the full machinery.

The Code

private static String mostFrequentNGram(String s, int n) {
    Map<String, Integer> map = new HashMap<>();
    String result = "";
    int maxCount = 0;
    for (int left = 0, right = 0; right < s.length(); right++) {
        if (right - left + 1 == n) {
            String sub = s.substring(left, right + 1);
            map.merge(sub, 1, Integer::sum);
            if (map.get(sub) > maxCount) {
                maxCount = map.get(sub);
                result = sub;
            }
            left++;
        }
    }
    return result;
}

A few things to note. map.merge(sub, 1, Integer::sum) is a concise Java idiom — it inserts 1 if the key is absent, otherwise adds 1 to the existing value. It replaces the more verbose getOrDefault / put pattern.

We update result only when a substring strictly exceeds the current maxCount. This naturally handles tie-breaking: the first n-gram to reach a given count claims it, and later ties don't override.

Complexity

Time: O(n · s.length()) We visit each position once, and at each position we create a substring of length n. Java's String.substring() copies characters, so each extraction is O(n).

Space: O(n · s.length()) The frequency map can store up to s.length() - n + 1 entries, each a string of length n.

Why This Matters

This problem is essentially a stripped-down version of LeetCode 1297: Maximum Number of Occurrences of a Substring. LeetCode 1297 adds a maxLetters constraint (limiting unique characters in the substring) and a maxSize parameter — but as we explore in the next post, the maxSize turns out to be a red herring. At its core, 1297 is this same fixed-size window frequency count, plus one extra check.