005 — First Unique Character in a String¶

Source¶

Original source: Classic frequency-count exercise
Platform: LeetCode — https://leetcode.com/problems/first-unique-character-in-a-string/
Topic: hash map / frequency count
Difficulty: Easy
Pattern: frequency counting
Basic idea inherited from: two-pass counting — আগে সব গোনো, তারপর গোনা নিয়ে দ্বিতীয়বার হাঁটো

1. Problem in simple words¶

একটা string s দেওয়া আছে। এর মধ্যে এমন প্রথম অক্ষরটা খুঁজে বের করো যেটা পুরো string-এ ঠিক একবার আছে, আর তার index ফেরত দাও। এমন কোনো অক্ষর না থাকলে -1 ফেরত দাও।

s = "leetcode"      →  0   ('l' প্রথম অক্ষর যেটা একবারই আছে)
s = "loveleetcode"  →  2   ('v' প্রথম unique, index 2)
s = "aabb"          →  -1  (কোনো অক্ষরই একবার নেই)

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 এমনিতেই রক্ষা পায়।

6. Real-life analogy¶

ভাবো একটা ভোটগণনা। আগে সব ব্যালট গুনে বের করো কোন প্রার্থী কয়টা ভোট পেল (first pass)। তারপর তালিকার শুরু থেকে নেমে এসে প্রথম যে প্রার্থী ঠিক একটা ভোট পেয়েছে তাকে চিহ্নিত করো (second pass)। গোনা শেষ না করে "প্রথম একবার-পাওয়া" কে তা বলা যায় না।

7. Visual explanation¶

s = "loveleetcode"। Pass 1-এ count, Pass 2-এ বাঁ থেকে ডান scan:

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

8. Example input and output¶

Input : "leetcode"      Output: 0
Input : "loveleetcode"  Output: 2
Input : "aabb"          Output: -1   (কোনো unique নেই)
Edge  : ""              Output: -1   (খালি string)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা index i-র জন্য s[i] পুরো string-এর বাকি অংশে আছে কি না খুঁজে দেখি; কোথাও না পেলে সেটাই প্রথম unique।

প্রতিটা 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-এ ভাগ করে দাও।

14. Step-by-step dry run¶

Input s = "aabb":

Pass 1: counts = {a:2, b:2}।
Pass 2: i=0 'a' count 2 → না; i=1 'a' count 2 → না; i=2 'b' count 2 → না; i=3 'b' count 2 → না।
কোনো count-1 পাওয়া যায়নি → return -1।

15. Python solution¶

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 অক্ষর নেই।

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!।

18. Time complexity¶

O(n) — দুটো pass, প্রতিটাই string-এর দৈর্ঘ্যে linear; lookup গড়ে O(1)।

19. Space complexity¶

O(k) — k = distinct অক্ষরের সংখ্যা (lowercase English হলে বড়জোর 26, কার্যত O(1))।

20. Common mistakes¶

এক pass-এ সারতে চাওয়া — গোনা শেষ না হলে "এটা unique" নিশ্চিত বলা যায় না; তাই দুই pass লাগে।
count map-এর iteration order-এর উপর ভরসা করা — "প্রথম" পেতে হলে দ্বিতীয় pass string-এর উপর হাঁটতে হবে, map-এর উপর নয়।
index-এর বদলে অক্ষর ফেরত দেওয়া — problem index চায়, character নয়।

21. Which basic problem this inherits from¶

ভিত্তি: frequency counting (Pattern 1) + two-pass পদ্ধতি — আগে গোনো, পরে গোনা নিয়ে সিদ্ধান্ত। ../patterns.md-র Pattern 1 আর ../concept.md-র counting snippet দেখো।

22. Similar harder problems¶

Sort Characters By Frequency — https://leetcode.com/problems/sort-characters-by-frequency/ (count করে frequency-ক্রমে সাজানো)
Top K Frequent Elements — https://leetcode.com/problems/top-k-frequent-elements/ (এই tracker-এর #11; count করে top-K বাছাই)
First Unique Number (stream) — https://leetcode.com/problems/first-unique-number/ (একই idea, streaming version)

23. Pattern learned¶

Two-pass frequency counting: Pass 1-এ সব গোনো, Pass 2-এ order রক্ষা করে গোনা নিয়ে সিদ্ধান্ত নাও।

24. Final summary¶

ভবিষ্যতের আমাকে: "প্রথম unique / একবার আছে এমন" শুনলেই দুই pass — আগে Counter, পরে string-এর order-এ হেঁটে count==1 ধরো। গোনা আর order-কে আলাদা করে ফেললেই O(n^2) নেমে আসে O(n)-এ।

25. JavaScript solution (with test cases)¶

দুই pass — প্রথমে Map-এ count, তারপর string-এর order-এ প্রথম count-1।

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-এ নয়।

26. TypeScript solution (with test cases)¶

function firstUniqChar(s: string): number {
  const counts = new Map<string, number>();      // char -> count
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (let i = 0; i < s.length; i++) {
    if (counts.get(s[i]) === 1) return i;
  }
  return -1;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(firstUniqChar("leetcode"), 0, "l");
expect(firstUniqChar("aabb"), -1, "none");
expect(firstUniqChar(""), -1, "empty");
console.log("সব TS test pass!");

TS টীকা: Map<string, number> typed, তাই get ফেরত দেয় number | undefined — ?? 0 দিয়ে undefined নিরাপদে সামলানো compiler-এ enforce হয়; return number বলে index/-1 ছাড়া কিছু ফেরত দেওয়া যায় না।

27. কোথায় কাজে লাগে (real-world use)¶

Stream first-unique: ইনকামিং event stream-এ প্রথম একবার-আসা item (first non-repeating) বের করা।
Log analysis: log line-এ প্রথম unique token/error code দ্রুত চিহ্নিত করা।
Text processing: document-এ প্রথম একবার-ব্যবহৃত শব্দ/অক্ষর খুঁজে highlight।
Cache/dedup heuristics: প্রথম অপুনরাবৃত্ত key বেছে priority দেওয়া।
Game/puzzle: প্রথম অনন্য চাল বা টোকেন নির্ধারণ।
Data validation: কোন field মান ঠিক একবার এসেছে তা খুঁজে anomaly detect।

মূল pattern: আগে সব গোনো, পরে order রক্ষা করে সিদ্ধান্ত নাও (two-pass counting) — count আর order আলাদা করলে O(n²) নেমে আসে O(n)-এ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।