Definition
The longest-substring-with-k-distinct-characters problem uses a variable-size sliding window backed by a frequency map that counts occurrences of each character in the current window. You expand the window on the right and, whenever the number of distinct characters exceeds k, shrink from the left, decrementing counts and removing characters whose count drops to zero, while tracking the maximum valid window length. This runs in linear time.
Imagine Rajesh scans a stream of single-letter transaction category codes and wants the longest continuous run that uses at most k different categories. He keeps a tally of how many of each category are currently in his run. He extends the run on the right, and whenever the run contains more than k distinct categories, he trims from the left, lowering tallies and dropping any category whose tally hits zero, until only k distinct categories remain. He remembers the longest valid run he achieves.
Understanding the Concepts
What is the problem?
Longest Substring with K Distinct Characters (Sliding Window with a Frequency Map). Given a string and a number k, find the length of the longest substring that contains at most k distinct characters. (GeeksforGeeks: Longest K unique characters substring)
How does the approach work?
This is a variable-size sliding window where the constraint is on the number of distinct characters, not a sum. We use a map from character to its count within the current window, and the map's size is the number of distinct characters.
We expand a right pointer across the string, and for each character we increment its count in the map. If the map now has more than k distinct keys, the window is invalid, so we shrink from the left: we decrement the count of the left character, and if its count reaches zero we remove it from the map, then advance the left pointer, repeating until the map has at most k keys again. After restoring validity, the current window from left to right is valid, so we update the maximum length if this window is longer.
A finance usage example: suppose the category stream is araaci and k is 2. Expanding, the window grows while using at most two distinct categories. When a third distinct category would enter, we shrink from the left until only two remain. The longest valid window for this input with k equal to 2 is araa, which has length 4 and uses only the two categories a and r.
The senior-level nuance: removing a character from the map exactly when its count drops to zero is what keeps the map size equal to the true distinct count, and forgetting that removal is a classic bug. The frequency map can be a hash map for a large alphabet or a fixed-size array for a small known alphabet, the latter being faster and lighter. Each pointer advances only forward, so even with the inner shrink loop the total time is linear. This same template, with the constraint changed, solves many related window problems, such as the fruits-into-baskets problem, which is exactly this with k equal to 2.
What is the banking use case?
The code defines a CategoryRunAnalyzer class with a longestRunWithKCategories method implementing the sliding window with a frequency map. A runnable demo seeds a category stream and a k value and logs the longest valid run length.
How do you implement this in Java?
// ─── File: src/main/java/com/bank/analytics/service/CategoryRunAnalyzer.java ───
package com.bank.analytics.service;
import java.util.HashMap;
import java.util.Map;
import java.util.logging.Logger;
// Finds the longest run with at most k distinct category codes.
public class CategoryRunAnalyzer {
private static final Logger log = Logger.getLogger(CategoryRunAnalyzer.class.getName());
public int longestRunWithKCategories(String codes, int k) {
if (codes == null || codes.isEmpty() || k <= 0) return 0;
Map<Character, Integer> counts = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < codes.length(); right++) {
char c = codes.charAt(right);
counts.merge(c, 1, Integer::sum); // expand: add/increment
while (counts.size() > k) { // too many distinct → shrink
char leftChar = codes.charAt(left);
int newCount = counts.get(leftChar) - 1;
if (newCount == 0) counts.remove(leftChar); // distinct count drops
else counts.put(leftChar, newCount);
left++;
}
best = Math.max(best, right - left + 1);
}
final int result = best;
log.info(() -> "Longest run with at most " + k + " categories = " + result);
return best;
}
}
// ─── File: src/main/java/com/bank/analytics/CategoryRunDemo.java ───
package com.bank.analytics;
import com.bank.analytics.service.CategoryRunAnalyzer;
import java.util.logging.Logger;
public class CategoryRunDemo {
private static final Logger log = Logger.getLogger(CategoryRunDemo.class.getName());
public static void main(String[] args) {
String codes = "araaci"; // category code stream
int k = 2;
CategoryRunAnalyzer analyzer = new CategoryRunAnalyzer();
int length = analyzer.longestRunWithKCategories(codes, k);
log.info(() -> "Longest consistent run in '" + codes + "' with k=" + k
+ " is " + length);
}
}
What is the project structure?
category-analytics-service/ ├── pom.xml ├── src/ │ ├── main/ │ │ ├── java/com/bank/analytics/ │ │ │ ├── CategoryRunDemo.java (runnable demo + main) │ │ │ └── service/ │ │ │ └── CategoryRunAnalyzer.java (window + freq map) │ │ └── resources/ │ │ └── application.yml │ └── test/ │ └── java/com/bank/analytics/ │ └── service/ │ └── CategoryRunAnalyzerTest.java
How do you build and run?
# Build
mvn clean package -DskipTests
# Run the demo
java -cp target/category-analytics-service-1.0.0.jar com.bank.analytics.CategoryRunDemo
# Expected
# INFO: Longest run with at most 2 categories = 4
# INFO: Longest consistent run in 'araaci' with k=2 is 4
What is the step-by-step walkthrough?
Input data: the category stream araaci and k equal to 2.
a, then r, giving the window ar with two distinct categories, which is within k. The best length becomes 2.a and another a, giving the window araa. The distinct categories are still only a and r, which is two, within k, so the best length becomes 4.c, making the window araac with three distinct categories, which exceeds k. The shrink loop removes from the left: it drops the first a, then r whose count reaches zero and is removed from the map, leaving the window aac with two distinct categories, a and c, back within k.i, making aaci with three distinct categories, exceeding k, so it shrinks from the left until two remain, giving a window like ci of length 2. No window beats the earlier length 4, so the method returns 4.Final output:
Oct 27, 2026 7:35:00 PM com.bank.analytics.CategoryRunDemo main
INFO: Longest run with at most 2 categories = 4
INFO: Longest consistent run in 'araaci' with k=2 is 4
What is the high-level design?
═══ HLD — Category Run Analytics ═══
┌────────────┐ REST ┌───────────────┐ call ┌────────────────────┐
│ Analytics │─────→│ API Gateway │─────→│ CategoryRun Svc │
│ Dashboard │ │ (auth, rate) │ │ (stateless ×3) │
└────────────┘ └───────────────┘ └─────────┬──────────┘
│ reads code stream
▼
┌────────────────────┐
│ Event store │
│ category_codes │
└────────────────────┘
What is the low-level design?
═══ LLD — CategoryRunAnalyzer ═══
┌─ Design Patterns Used ───────────────────────────────────┐
│ Variable window + frequency map (distinct-count rule) │
│ WHY: map.size() == distinct count → O(n) scan │
└───────────────────────────────────────────────────────────┘
┌─ SOLID Principles ───────────────────────────────────────┐
│ S: analyzer only computes the longest valid run │
│ O: change constraint (k, charset) without rewrite │
└───────────────────────────────────────────────────────────┘
── Class Diagram ──────────────────────────────────────────
┌───────────────────────────────────────┐ uses ┌──────────────┐
│ CategoryRunAnalyzer │─────▶│ Map<Char,Int>│
│ ──────────────────────────────────── │ │ freq counts │
│ + longestRunWithKCategories(String,k)│ └──────────────┘
│ : int │
└───────────────────────────────────────┘
O(n) time, O(k) space
── State Diagram: window + map ───────────────────────────
[expand right, map.merge] ──map.size>k──→ shrink left, drop zero-count
──map.size<=k─→ update best
── Call Chain ─────────────────────────────────────────────
1. Demo.main seeds "araaci", k=2
2. → longestRunWithKCategories(codes, 2)
3. expand/shrink with freq map; track best
4. → return 4
5. → log longest run
What is the time and space complexity?
Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.
What are common mistakes?
Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.
What are the edge cases?
Edge cases include empty input, single element input, all identical elements, and boundary values.
What should a senior engineer know?
A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.
Visual Overview
Input: "araaci", k=2
│ expand a,r → "ar" {a:1,r:1} len2 best=2
│ expand a,a → "araa" {a:3,r:1} len4 best=4
│ expand c → "araac" {a,r,c}=3 >k → shrink left (drop a, drop r) → "aac" {a,c}
│ expand i → "aaci" >k → shrink → window len2
▼
longest = 4
Key Takeaway
The longest-substring-with-k-distinct-characters problem is a variable-size sliding window where the constraint is on the number of distinct characters rather than on a sum, and I back the window with a frequency map that counts how many of each character are currently inside it. The size of that map is exactly the number of distinct characters in the window, which is the quantity I need to keep at or below k.
I expand a right pointer across the string, and for each character I increment its count in the map. Whenever the map's size exceeds k, meaning the window now has too many distinct characters, I shrink from the left: I decrement the count of the leftmost character, and if its count reaches zero I remove it from the map entirely, then advance the left pointer, repeating until the map is back to at most k keys. Once the window is valid again, I update the maximum length with the current window span. Because each pointer only moves forward, the whole scan is linear time even with the inner shrink loop.
In my banking project at the National Bank of India I used this on the analytics team. We logged a stream of single-letter transaction category codes for an account and wanted the longest continuous run that stayed within at most k distinct categories, because such runs indicated periods of consistent account behavior that were worth profiling. Over long streams a quadratic check of every run was too slow, and the sliding window with a frequency map found the longest valid run in a single pass.
The senior-level point I stress is the removal rule, which is where people most often introduce a bug. I must remove a character from the map at exactly the moment its count drops to zero, because otherwise the map's size no longer equals the true distinct count and the whole constraint check becomes wrong. I also note that for a small known alphabet I can replace the hash map with a fixed-size array for speed and lower memory, and that this exact template with the constraint simply set to k equal to two solves the fruits-into-baskets problem. Recognizing that a whole family of problems is the same window template with a different constraint is what lets me solve them quickly and correctly.
Remember one sentence: understand the core algorithm and apply it to banking domain problems.
---