What is the brute force approach and complexity for Longest Substring with K Unique Characters?

For each start, extend right while tracking distinct letters with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Longest Substring with K Unique Characters?

Grow right; shrink while distinct > k; record length only when distinct == k with optimal time complexity O(N) and space complexity O(1).

Longest Substring with K Unique Characters

Q: How do you identify the pattern for Longest Substring with K Unique Characters?

Look for key signals in the prompt: "longest substring" indicates Contiguous range, maximise its length → variable window.; "exactly k unique characters" indicates The rule is about how many different letters are inside → count map + distinct counter.; "return −1 if not possible" indicates Some windows are kept but never counted. Start best at −1 and record only on an exact match..

Medium·GeeksforGeeks Pro OnlyBasic Reinforcement

GeeksforGeeks

Problem Statement

You are given a string s of lowercase letters and a number k.

Find the longest substring (contiguous part of s) that contains exactly k different letters. Return its length.

If no substring has exactly k different letters, return −1.

The function is longestKSubstr(s, k) and returns an int.

Input

A string s of lowercase English letters and an integer k.

Output

The length of the longest substring with exactly k distinct letters, or -1 if there is none.

Example 1

Input: s = "aabacbebebe", k = 3

Output: 7

"cbebebe" uses exactly 3 letters (c, b, e) and has length 7. No longer substring has exactly 3 letters.

Example 2

Input: s = "aaaa", k = 2

Output: -1

The whole string only has 1 distinct letter, so no substring can have exactly 2.

Example 3

Input: s = "aabaaab", k = 2

Output: 7

The whole string uses exactly 2 letters (a and b).

Constraints

• 1 ≤ s.length ≤ 10^5
• 1 ≤ k ≤ 26
• s contains only lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“longest substring”

→ Contiguous range, maximise its length → variable window.

“exactly k unique characters”

→ The rule is about how many different letters are inside → count map + distinct counter.

“return −1 if not possible”

→ Some windows are kept but never counted. Start best at −1 and record only on an exact match.

Approach Complexity Ladder

Brute Force — grow from every startO(N²)O(1)

For each start, extend right while tracking distinct letters

Optimal — sliding window, shrink on > k, record on == kO(N)O(1)

Grow right; shrink while distinct > k; record length only when distinct == k

Brute Force Intuition

Try every starting index. From each start, extend the end one letter at a time, keeping a count array and the number of distinct letters. Whenever distinct is exactly k, record the length. Once distinct goes above k, stop — growing can't bring it back down.

Recognition rule for this sub-pattern:

Validity depends on the counts of things inside the window (distinct types, most frequent char, required letters). Keep a count map that updates on every add/remove.

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Fruit Into Baskets Longest Repeating Character Replacement