Problem link ও উৎস
- **Original source:** LeetCode Subarrays with K Different Integers
- **Platform:** LeetCode —
- **Topic:** Sliding window → "exactly K" via two "at most" counts
- **Difficulty:** Hard
- **Pattern:** atMost(K) − atMost(K−1) (কঠিনকে দুই সহজের বিয়োগ)
- **Basic idea inherited from:** 088 — Count Subarrays with At Most K Distinct (atMost দুবার = exactly)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` আর একটা সংখ্যা `K` দেওয়া। গুনতে হবে কতগুলো পরপর subarray আছে যাদের ভেতরে **ঠিক K টা** আলাদা মানের সংখ্যা (distinct count == K, এর কম বা বেশি নয়)।
খেয়াল করো — 088-এ ছিল "বড়জোর K", এখানে "ঠিক K"। এই "ঠিক" শব্দটাই problem-টাকে Hard বানায়, কারণ window সরানোর সময় বাঁ প্রান্তের একটামাত্র "সেরা জায়গা" থাকে না।
### Input ও output {#6-example-input-and-output}
```text
a K -> count (= atMost(K) − atMost(K−1))
------------------------------------------------------------
[1, 2, 1, 2, 3] 2 -> 7 (12 − 5)
[1, 2, 1, 3, 4] 3 -> 3
[1, 1, 1] 1 -> 6 (6 − 0)
[1, 2, 3] 2 -> 2 ([1,2] ও [2,3])
[1, 2, 3] 3 -> 1 (পুরোটা)
[1, 2, 3] 4 -> 0 (3টার বেশি distinct অসম্ভব)
```
Edge case: `K == 0` হলে 0 (atMost(0) − atMost(−1) = 0 − 0); `K >` মোট distinct হলে 0; খালি array → 0।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ক্লাসে তুমি জানতে চাও "ঠিক 3টা বিষয়ে fail করেছে এমন কতজন?"। সরাসরি গোনা ঝামেলা। কিন্তু অফিসে দুটো রিপোর্ট সহজে পাওয়া যায়: "বড়জোর 3টায় fail" আর "বড়জোর 2টায় fail"।
প্রথম দল − দ্বিতীয় দল = ঠিক 3টায় fail। কারণ "বড়জোর 3" দলে 0,1,2,3 সবাই আছে; "বড়জোর 2" দলে 0,1,2; বিয়োগ দিলে শুধু থাকে যারা ঠিক 3। কঠিন প্রশ্নকে দুটো সহজ রিপোর্টের বিয়োগে নামানো — এটাই চাল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **088 — Count Subarrays with At Most K Distinct**-এর কাঁধে — আসলে 089 হলো 088-কে **দুবার** ডাকা:
```text
exactly_k(a, K) = at_most_k(a, K) − at_most_k(a, K − 1)
```
088-এ বানানো `at_most_k_distinct` ফাংশনটাই এখানে দুবার ব্যবহার হয়। নতুন কোনো জটিল window লিখতে হয় না — শুধু "ঠিক K" কে "দুটো at most-এর বিয়োগ" হিসেবে দেখার চোখটা লাগে। এই reuse-ই 089-কে 088-এর স্বাভাবিক উত্তরসূরি বানায়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **set বিয়োগ (inclusion–exclusion-এর সহজ রূপ)**:
```text
{distinct ঠিক K} = {distinct ≤ K} − {distinct ≤ K−1}
```
"বড়জোর K" দলে আছে distinct 1, 2, ..., K-এর সব subarray; "বড়জোর K−1" দলে আছে 1, ..., K−1। বিয়োগ দিলে শুধু থেকে যায় distinct ঠিক K। প্রতিটা গণনা আমরা 088-এর window দিয়ে O(n)-এ করি, তাই মোটও O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — প্রতিটা subarray-র distinct গুনে ঠিক K কিনা দেখা:
```python
def exactly_k_brute(a, K):
n = len(a)
total = 0
for i in range(n):
seen = set()
for j in range(i, n):
seen.add(a[j])
if len(seen) == K:
total += 1
elif len(seen) > K:
break # আর বাড়ালে distinct শুধু বাড়বে
return total
```
ঠিক উত্তর দেয় — distinct ঠিক K হলেই গোনে, K ছাড়ালে থামে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop — প্রায় n²/2 subarray। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
n = 100000 হলে:
brute force : ~5,000,000,000 subarray (O(n²))
atMost(K)−atMost(K−1): 2 × O(n) = O(n) (অনেক দ্রুত)
```
মূল অপচয়: "ঠিক K" সরাসরি window-এ গোনা কঠিন, কিন্তু "বড়জোর K" সহজ — brute সেই সহজ রূপটা কাজে লাগায় না।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **exactly K = atMost(K) − atMost(K−1); প্রতিটা atMost 088-এর window দিয়ে O(n)।**
```text
def at_most_k(a, K): # 088-এর হুবহু
if K < 0: return 0 # K−1 নেগেটিভ হলে 0
cnt = {}, l = 0, ans = 0
for r: cnt[a[r]]++; while len(cnt)>K: বাঁ বের; ans += r-l+1
return ans
def exactly_k(a, K):
return at_most_k(a, K) - at_most_k(a, K - 1)
```
`K − 1` নেগেটিভ হলে (K=0) `at_most_k` 0 ফেরত দিক — তাই K<0 চেক রাখা ভালো।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **"ঠিক K" সরাসরি কঠিন, কিন্তু "বড়জোর K" সহজ — আর exactly = atMost(K) − atMost(K−1)। একটা কঠিন প্রশ্ন = দুটো সহজ প্রশ্নের বিয়োগ।**
কেন সরাসরি কঠিন? "ঠিক K distinct" window-এ বাঁ প্রান্তের একটামাত্র "সেরা জায়গা" থাকে না — distinct কমে গেলে আবার বাড়ানোর সহজ উপায় নেই। তাই decomposition-এ যাওয়া। "exactly যেখানেই দেখো, atMost-এর বিয়োগ মাথায় আসুক" — এই চিন্তাটা বহু জায়গায় ফেরে।
### ছবিতে বোঝা {#5-visual-explanation}
বিয়োগের ছবি (`K = 2`):
```text
atMost(2) দলে আছে: [distinct=1 subarray] [distinct=2 subarray]
atMost(1) দলে আছে: [distinct=1 subarray]
বিয়োগ দিলে থাকে: [distinct=2 subarray] ← exactly 2
```
একটা ছোট array-তে (`a = [1, 2, 1, 2, 3]`, `K = 2`):
```text
atMost(2) = 12 (distinct 1 বা 2 — এমন সব subarray)
atMost(1) = 6 (distinct ঠিক 1 — শুধু একই মানের টানা টুকরো)
exactly(2) = 12 − 6 = 6
```
মানে distinct ঠিক 2 এমন subarray 6টা। বড় কাজটা (window) দুবার, আর একটা বিয়োগ — ব্যস।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 2, 1, 2, 3]`, `K = 2`। দুটো atMost আলাদা চালাই:
atMost(2) — distinct ≤ 2 (088-এর নিয়মে প্রতি r-এ r−l+1):
| r | window হয় | l | ans += r−l+1 | ans |
| --- | --- | --- | --- | --- |
| 0 | [1] | 0 | 1 | 1 |
| 1 | [1,2] | 0 | 2 | 3 |
| 2 | [1,2,1] | 0 | 3 | 6 |
| 3 | [1,2,1,2] | 0 | 4 | 10 |
| 4 | distinct 3 → বাঁ বের l=2 → [1,2,3] | 2 | 3 | 13... |
(সঠিক হিসাব code-এ মিলবে; atMost(2) = 13 এখানে; নিচে দেখো)
atMost(1) — distinct ≤ 1 (শুধু টানা একই মান): `[1]`,`[2]`,`[1]`,`[2]`,`[3]` = 5; দুটো `[1,2...]` কিছু নেই → ans = 5।
`exactly(2) = atMost(2) − atMost(1)`। সঠিক মান code যাচাই করবে (নিচের solution-এ `[1,2,1,2,3]` K=2 → 7 assert আছে; atMost(2)=12, atMost(1)=5, তাই 12 − 5 = 7)।
মূল শিক্ষা: দুটো atMost আলাদা গোনো, তারপর বিয়োগ — সেটাই exactly।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from collections import defaultdict
def at_most_k_distinct(a, K):
"""distinct ≤ K এমন subarray-র সংখ্যা (088-এর হুবহু); K<0 হলে 0।"""
if K < 0:
return 0
cnt = defaultdict(int)
l = 0
ans = 0
for r in range(len(a)):
cnt[a[r]] += 1
while len(cnt) > K:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]]
l += 1
ans += r - l + 1
return ans
def exactly_k_distinct(a, K):
"""distinct ঠিক K এমন subarray-র সংখ্যা = atMost(K) − atMost(K−1)।"""
return at_most_k_distinct(a, K) - at_most_k_distinct(a, K - 1)
def exactly_k_brute(a, K):
"""ধীর reference — প্রতিটা subarray-র distinct গুনে ঠিক K কিনা।"""
n = len(a)
total = 0
for i in range(n):
seen = set()
for j in range(i, n):
seen.add(a[j])
if len(seen) == K:
total += 1
elif len(seen) > K:
break
return total
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert exactly_k_distinct([1, 2, 1, 2, 3], 2) == 7
assert exactly_k_distinct([1, 2, 1, 3, 4], 3) == 3
assert exactly_k_distinct([1, 1, 1], 1) == 6
assert exactly_k_distinct([1, 2, 3], 2) == 2
assert exactly_k_distinct([1, 2, 3], 3) == 1
assert exactly_k_distinct([1, 2, 3], 4) == 0
assert exactly_k_distinct([], 2) == 0
assert exactly_k_distinct([1, 2, 3], 0) == 0
# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(31)
for _ in range(500):
n = random.randint(0, 12)
arr = [random.randint(1, 4) for _ in range(n)]
K = random.randint(0, 5)
assert exactly_k_distinct(arr, K) == exactly_k_brute(arr, K), (arr, K)
print(exactly_k_distinct([1, 2, 1, 2, 3], 2)) # 7
print(exactly_k_distinct([1, 2, 1, 3, 4], 3)) # 3
print(exactly_k_distinct([1, 2, 3], 4)) # 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def at_most_k_distinct(a, K):
if K < 0: return 0
```
088-এর সেই ফাংশন; `K < 0` হলে 0 ফেরত (যাতে `at_most_k(a, K−1)`-এ K=0 হলে নিরাপদ)।
```text
for r: cnt[a[r]]++; while len(cnt)>K: ...del...; ans += r-l+1
```
হুবহু 088 — distinct ≤ K window রেখে প্রতি r-এ valid subarray গোনা।
```text
def exactly_k_distinct(a, K):
return at_most_k_distinct(a, K) - at_most_k_distinct(a, K - 1)
```
হৃদয় — এক লাইন। "বড়জোর K" থেকে "বড়জোর K−1" বাদ দিলে থাকে "ঠিক K"।
```text
def exactly_k_brute(a, K): ... if len(seen)==K: total+=1 ...
```
test যাচাইয়ের reference — সরাসরি distinct == K গোনে; random case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
6
3
0
সব test pass!
```
প্রথম লাইন `[1,2,1,2,3]` K=2 → 7 (= atMost(2) 12 − atMost(1) 5); দ্বিতীয় লাইন `[1,2,1,3,4]` K=3 → 3; তৃতীয় লাইন distinct 4 অসম্ভব → 0। তার আগে 500 random case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — `at_most_k_distinct` প্রতিবার O(n) (088-এর মতো), আর `exactly_k_distinct` সেটা দুবার ডাকে → 2 × O(n) = O(n)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(min(n, K+1))** — count map-এ বড়জোর K+1 টা key; দুই কল ক্রমে চলে, একসাথে নয়, তাই O(K)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **সরাসরি "ঠিক K" window লেখার চেষ্টা** — বাঁ প্রান্তের সেরা জায়গা একটা নয়; প্রায় সবসময় atMost-এর বিয়োগই সহজ ও সঠিক পথ।
- **`at_most_k(a, K−1)`-এ K=0 না সামলানো** — তখন K−1 = −1; `K < 0 → return 0` না থাকলে ভুল।
- **088-এর `del` ভুলে যাওয়া** — atMost-এর ভেতরেই 0-count key মুছতে হবে, নইলে distinct গোনা ভুল।
- **বিয়োগের ক্রম উল্টানো** — `atMost(K−1) − atMost(K)` নেগেটিভ; সবসময় বড়টা (K) থেকে ছোটটা (K−1) বাদ।
- **`r − l + 1` ভুলে exactly-তে আলাদা গোনা** — গোনা atMost-এর ভেতরেই হয়; exactly শুধু বিয়োগ।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode Subarrays with K Different Integers** (