Problem link ও উৎস
- **Original source:** Classic frequency-count exercise
- **Platform:** LeetCode —
- **Topic:** hash map / frequency count
- **Difficulty:** Easy
- **Pattern:** frequency counting
- **Basic idea inherited from:** two-pass counting — আগে সব গোনো, তারপর গোনা নিয়ে দ্বিতীয়বার হাঁটো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` দেওয়া আছে। এর মধ্যে এমন প্রথম অক্ষরটা খুঁজে বের করো যেটা পুরো string-এ **ঠিক একবার** আছে, আর তার **index** ফেরত দাও। এমন কোনো অক্ষর না থাকলে `-1` ফেরত দাও।
```text
s = "leetcode" → 0 ('l' প্রথম অক্ষর যেটা একবারই আছে)
s = "loveleetcode" → 2 ('v' প্রথম unique, index 2)
s = "aabb" → -1 (কোনো অক্ষরই একবার নেই)
```
### Input ও output {#8-example-input-and-output}
```text
Input : "leetcode" Output: 0
Input : "loveleetcode" Output: 2
Input : "aabb" Output: -1 (কোনো unique নেই)
Edge : "" Output: -1 (খালি string)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা ভোটগণনা। আগে সব ব্যালট গুনে বের করো কোন প্রার্থী কয়টা ভোট পেল (first pass)। তারপর তালিকার শুরু থেকে নেমে এসে প্রথম যে প্রার্থী ঠিক একটা ভোট পেয়েছে তাকে চিহ্নিত করো (second pass)। গোনা শেষ না করে "প্রথম একবার-পাওয়া" কে তা বলা যায় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **two-pass counting**-এর উপর। প্রথম pass-এ frequency counting (Pattern 1) দিয়ে প্রতিটা অক্ষর কয়বার আছে গুনি; দ্বিতীয় pass-এ সেই গোনা নিয়ে string-এর উপর আবার হেঁটে প্রথম count-1 অক্ষরটা ধরি। "আগে পুরো তথ্য জোগাড়, পরে সিদ্ধান্ত" — এটাই two-pass-এর মূল।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: "unique" মানে **count ঠিক 1**। কিন্তু আমরা শুধু unique অক্ষর চাই না — চাই *বাঁদিক থেকে প্রথম* unique-টা। তাই index-এর ক্রম রক্ষা করতে হবে। চাবি: count জানতে পুরো string লাগে, কিন্তু "প্রথম" পেতে আবার বাঁ থেকে ডান ক্রমে হাঁটতে হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **frequency map** — `collections.Counter` (`char → count`)। আর "প্রথম" খুঁজতে আমরা string-এর স্বাভাবিক index-ক্রমকেই কাজে লাগাই, তাই আলাদা structure লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Counter এক pass-এ সব count দেয়, আর পরে যেকোনো অক্ষরের count জানা O(1)। দ্বিতীয় pass-এ string-এর ক্রমেই হাঁটি বলে যেটা প্রথম পাই সেটাই বাঁদিক থেকে প্রথম unique — index-এর order এমনিতেই রক্ষা পায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা index `i`-র জন্য `s[i]` পুরো string-এর বাকি অংশে আছে কি না খুঁজে দেখি; কোথাও না পেলে সেটাই প্রথম unique।
```text
প্রতিটা i-র জন্য:
s[i] কি s-এর অন্য কোনো জায়গায় আছে?
না থাকলে → return i
return -1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা অক্ষরের জন্য পুরো string scan = মোট **O(n^2)**। একই অক্ষরের count আমরা বারবার নতুন করে গুনছি — অথচ একবার সব গুনে রাখলে প্রতিটা lookup O(1) হয়ে যেত। সেই পুনরাবৃত্ত গোনাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **count আর order আলাদা করে ফেলা যায়**। প্রথমে সব count জোগাড় করো (order ভুলে), তারপর string-এর স্বাভাবিক order-এ হেঁটে প্রথম count-1 ধরো। এক problem-কে দুটো সহজ pass-এ ভাঙা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Pass 1: `Counter(s)` দিয়ে প্রতিটা অক্ষরের গণনা বানাও। Pass 2: index 0 থেকে শুরু করে প্রথম যে অক্ষরের count 1, তার index ফেরত দাও। দ্বিতীয় pass string-এর order-এ চলে বলে "প্রথম" আপনাআপনি ঠিক থাকে। কোনো count-1 না পেলে `-1`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা অক্ষর কি unique" — এই প্রশ্ন প্রতিবার পুরো string স্ক্যান করে; বদলে আগে একবারে সব count জমাও, তারপর শুধু "count == 1?" জিজ্ঞেস করো। গোনা আর খোঁজাকে দুটো আলাদা pass-এ ভাগ করে দাও।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "loveleetcode"`। Pass 1-এ count, Pass 2-এ বাঁ থেকে ডান scan:
```text
Pass 1 count: {l:2, o:2, v:1, e:4, t:1, c:1, d:1}
Pass 2 (index ক্রমে):
i=0 'l' count 2 → না
i=1 'o' count 2 → না
i=2 'v' count 1 → হ্যাঁ! return 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s = "aabb"`:
1. Pass 1: `counts = {a:2, b:2}`।
2. Pass 2: `i=0 'a'` count 2 → না; `i=1 'a'` count 2 → না; `i=2 'b'` count 2 → না; `i=3 'b'` count 2 → না।
3. কোনো count-1 পাওয়া যায়নি → return `-1`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import Counter
def first_uniq_char(s):
counts = Counter(s) # Pass 1: প্রতিটা অক্ষর কয়বার
for i, ch in enumerate(s): # Pass 2: বাঁ থেকে ডান
if counts[ch] == 1: # প্রথম যেটা একবার
return i
return -1 # কোনো unique নেই
# ---- tests ----
assert first_uniq_char("leetcode") == 0
assert first_uniq_char("loveleetcode") == 2
assert first_uniq_char("aabb") == -1
assert first_uniq_char("") == -1 # খালি string
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `counts = Counter(s)` — Pass 1; এক ঝটকায় `char → count` map।
- `for i, ch in enumerate(s)` — Pass 2; string-এর index-ক্রমে হাঁটি, তাই "প্রথম" রক্ষা পায়।
- `if counts[ch] == 1` — এই অক্ষর কি পুরো string-এ ঠিক একবার?
- `return i` — হ্যাঁ হলে সেটাই বাঁদিক থেকে প্রথম unique, তার index দাও।
- `return -1` — loop শেষেও কেউ না মিললে, কোনো unique অক্ষর নেই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"leetcode"`: count `{l:1,e:3,t:1,c:1,o:1,d:1}`; index 0-এর `'l'` count 1 → `0`। `"loveleetcode"`: index 0,1 (`l,o`) count 2, index 2-এর `'v'` count 1 → `2`। `"aabb"`: সব count 2 → `-1`। `""`: loop চলে না → `-1`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই pass — প্রথমে `Map`-এ count, তারপর string-এর order-এ প্রথম count-1।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// index of first character that appears exactly once (-1 if none)
function firstUniqChar(s) {
const counts = new Map(); // Pass 1: char -> count
for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
for (let i = 0; i < s.length; i++) { // Pass 2: বাঁ থেকে ডান
if (counts.get(s[i]) === 1) return i;
}
return -1; // কোনো unique নেই
}
// ---- test cases (example + edge) ----
assert(firstUniqChar("leetcode") === 0, "l");
assert(firstUniqChar("loveleetcode") === 2, "v");
assert(firstUniqChar("aabb") === -1, "none"); // edge
assert(firstUniqChar("") === -1, "empty"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** counter বানাতে `Map` + `counts.get(ch) || 0` idiom; plain object-ও চলত কিন্তু `Map` key-ধরনে নিরাপদ। "প্রথম" পেতে দ্বিতীয় pass অবশ্যই *string*-এর index-ক্রমে চালাও, Map-এর iteration order-এ নয়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function firstUniqChar(s: string): number {
const counts = new Map