Iterative Stream Minimum — Problem Statement & Solution Guide

StringsHardCharacter Frequency Map

TimeO(n)

SpaceO(1)

Problem Description

You are processing a continuous stream of character frequencies derived from a text log. The system tracks the minimum frequency value observed at each step of the stream. Given a string s consisting of lowercase English letters, compute the cumulative sum of the minimum character frequency encountered so far after processing each character in the string from left to right.

Specifically, for each index i from 0 to n-1, consider the substring s[0...i]. Let freq(c) be the count of character c in this substring. Let minFreq(i) be the minimum value among all freq(c) for characters c that appear in s[0...i]. The final result is the sum of minFreq(i) for all i from 0 to n-1.

Note: Only characters that have appeared at least once in the current prefix are considered when determining the minimum frequency. If a character has not appeared yet, it is ignored in the minimum calculation for that step.

DSA Pattern Breakdown

"Iterative Stream Minimum"

hard

WHY DOES IT MATTER?

Incremental frequency tracking reduces redundant work and ensures each character is processed only once, which is essential for real-time stream processing where latency must be bounded. Without this pattern, the system would become a bottleneck as the input size grows.

OPTIMIZATION CHALLENGE

The key insight is that the alphabet size is constant, so scanning the 26 counters to find the minimum is effectively O(1). This eliminates the need for more complex data structures and keeps the algorithm simple and fast.

REAL-WORLD CONNECTION

Consider a monitoring system that tracks the least-used CPU core across a cluster. Each core’s usage count is updated as tasks are scheduled, and the system continuously reports the core with the minimal load. The same incremental update logic applies, ensuring the monitoring stays responsive.

When explaining this to an interviewer, emphasize that you maintain a running minimum and only recompute it when the character that was just incremented was the previous minimum. This shows you understand how to avoid unnecessary work.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem requires maintaining the minimum frequency among all characters seen so far while processing a stream of lowercase letters. A naive approach would recompute the frequency of every character after each new input character, leading to an O(n^2) time complexity for a string of length n. This is impractical for large logs where n can be millions. The optimal paradigm exploits the fact that the alphabet size is constant (26 lowercase English letters). By keeping an array of 26 counters that are incremented as each character arrives, we can update the current minimum in constant time or by scanning the 26 counters, which is still O(1) per step. Thus the overall time complexity becomes O(n) and the space usage remains O(1). This incremental frequency tracking pattern is a classic example of turning a quadratic problem into linear time by avoiding redundant work and leveraging domain constraints (fixed alphabet).

Interview Questions on This Problem

Q1How would you adapt this algorithm if the input alphabet were not fixed but could contain any Unicode character?

You would replace the fixed-size array with a hash map (e.g., unordered_map in C++ or a dictionary in Python) that maps characters to their counts. The min calculation would then involve iterating over the map entries, which is O(k) where k is the number of distinct characters seen so far. Since k can grow with the input, the per-step cost becomes O(k) instead of O(1), but it remains efficient for typical workloads where k is much smaller than n.

Q2What changes would you make if the stream could also contain deletions of characters?

You would need to decrement the count for the deleted character and then recompute the minimum. This could be done by maintaining a multiset of frequencies or a priority queue that supports deletions. Each deletion would require updating the data structure and possibly rebalancing it, leading to O(log k) per operation if a balanced BST is used.

Q3In a distributed log ingestion system, how could you parallelize the computation of the cumulative minimum frequency?

You could partition the stream by character or by time windows, compute local frequency counts and local minimums in parallel, and then merge the results using a reduce step that aggregates counts and recomputes the global minimum. Since the alphabet is small, merging is cheap: you sum counts per character across partitions and then find the minimum of the summed counts.

Examples

Example 1

Input

s = "aab"

Output

Explanation: Step 0: s[0..0] = "a". Freqs: {a:1}. Min = 1. Sum = 1. Step 1: s[0..1] = "aa". Freqs: {a:2}. Min = 2. Sum = 1 + 2 = 3. Step 2: s[0..2] = "aab". Freqs: {a:2, b:1}. Min = 1. Sum = 3 + 1 = 4. Final Output: 4.

Example 2

Input

s = "abc"

Output

Explanation: Step 0: s[0..0] = "a". Freqs: {a:1}. Min = 1. Sum = 1. Step 1: s[0..1] = "ab". Freqs: {a:1, b:1}. Min = 1. Sum = 1 + 1 = 2. Step 2: s[0..2] = "abc". Freqs: {a:1, b:1, c:1}. Min = 1. Sum = 2 + 1 = 3. Final Output: 3.

Example 3

Input

s = "aabbcc"

Output

Explanation: Step 0: "a" -> {a:1}, min=1, sum=1. Step 1: "aa" -> {a:2}, min=2, sum=3. Step 2: "aab" -> {a:2, b:1}, min=1, sum=4. Step 3: "aabb" -> {a:2, b:2}, min=2, sum=6. Step 4: "aabbc" -> {a:2, b:2, c:1}, min=1, sum=7. Step 5: "aabbcc" -> {a:2, b:2, c:2}, min=2, sum=9. Wait, let's re-calculate carefully. Step 0: "a" -> min(1)=1. Sum=1. Step 1: "aa" -> min(2)=2. Sum=1+2=3. Step 2: "aab" -> min(2,1)=1. Sum=3+1=4. Step 3: "aabb" -> min(2,2)=2. Sum=4+2=6. Step 4: "aabbc" -> min(2,2,1)=1. Sum=6+1=7. Step 5: "aabbcc" -> min(2,2,2)=2. Sum=7+2=9. Correction: The output should be 9. Let me re-verify the example logic. Yes, 9 is correct. I will update the output to 9.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters only
The sum of frequencies for any prefix is at most 10^5

Optimal Approach & Strategy

Maintain a 26‑element frequency array and update the minimum after each increment, either by scanning the array or by updating only when necessary.

Brute Force Approach

Recompute the frequency of every character from scratch after each new character, then find the minimum among those frequencies.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @return {number}
 */
var solve = function(s) {
    const freq = new Array(26).fill(0);
    let total = 0;
    
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 97;
        freq[charCode]++;
        
        let minFreq = Infinity;
        for (let j = 0; j < 26; j++) {
            if (freq[j] > 0) {
                minFreq = Math.min(minFreq, freq[j]);
            }
        }
        
        if (minFreq !== Infinity) {
            total += minFreq;
        }
    }
    
    return total;
};

class Solution {
public:
    int solve(string s) {
        vector<int> freq(26, 0);
        int total = 0;
        for (char c : s) {
            freq[c - 'a']++;
            int minFreq = INT_MAX;
            for (int i = 0; i < 26; i++) {
                if (freq[i] > 0) {
                    minFreq = min(minFreq, freq[i]);
                }
            }
            if (minFreq != INT_MAX) {
                total += minFreq;
            }
        }
        return total;
    }
};

class Solution {
    public int solve(String s) {
        int[] freq = new int[26];
        int total = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freq[c - 'a']++;
            
            int minFreq = Integer.MAX_VALUE;
            for (int j = 0; j < 26; j++) {
                if (freq[j] > 0) {
                    minFreq = Math.min(minFreq, freq[j]);
                }
            }
            
            if (minFreq != Integer.MAX_VALUE) {
                total += minFreq;
            }
        }
        
        return total;
    }
}

class Solution:
    def solve(self, s: str) -> int:
        freq = [0] * 26
        total = 0
        
        for c in s:
            freq[ord(c) - ord('a')] += 1
            
            min_freq = float('inf')
            for i in range(26):
                if freq[i] > 0:
                    min_freq = min(min_freq, freq[i])
            
            if min_freq != float('inf'):
                total += min_freq
        
        return total

/**
 * @param {string} s
 * @return {number}
 */
var solve = function(s) {
    const freq = new Array(26).fill(0);
    let total = 0;
    
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 97;
        freq[charCode]++;
        
        let minFreq = Infinity;
        for (let j = 0; j < 26; j++) {
            if (freq[j] > 0) {
                minFreq = Math.min(minFreq, freq[j]);
            }
        }
        
        if (minFreq !== Infinity) {
            total += minFreq;
        }
    }
    
    return total;
};

Asked in Top Tech Interviews

MetaAtlassian

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Iterative Stream Minimum Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Iterative Stream Minimum — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor