005 — First Unique Character in a String

Problem link ও উৎস

• 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 — আগে সব গোনো, তারপর গোনা নিয়ে দ্বিতীয়বার হাঁটো

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ

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

Input ও output

উদাহরণ

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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা দাঁড়িয়ে আছে two-pass counting-এর উপর। প্রথম pass-এ frequency counting (Pattern 1) দিয়ে প্রতিটা অক্ষর কয়বার আছে গুনি; দ্বিতীয় pass-এ সেই গোনা নিয়ে string-এর উপর আবার হেঁটে প্রথম count-1 অক্ষরটা ধরি। "আগে পুরো তথ্য জোগাড়, পরে সিদ্ধান্ত" — এটাই two-pass-এর মূল।

ভেতরের যুক্তি

লুকানো logic: "unique" মানে count ঠিক 1। কিন্তু আমরা শুধু unique অক্ষর চাই না — চাই বাঁদিক থেকে প্রথম unique-টা। তাই index-এর ক্রম রক্ষা করতে হবে। চাবি: count জানতে পুরো string লাগে, কিন্তু "প্রথম" পেতে আবার বাঁ থেকে ডান ক্রমে হাঁটতে হয়।

কী দিয়ে তথ্য রাখব

একটা frequency map — collections.Counter (char → count)। আর "প্রথম" খুঁজতে আমরা string-এর স্বাভাবিক index-ক্রমকেই কাজে লাগাই, তাই আলাদা structure লাগে না।

এটি কেন উপযুক্ত

Counter এক pass-এ সব count দেয়, আর পরে যেকোনো অক্ষরের count জানা O(1)। দ্বিতীয় pass-এ string-এর ক্রমেই হাঁটি বলে যেটা প্রথম পাই সেটাই বাঁদিক থেকে প্রথম unique — index-এর order এমনিতেই রক্ষা পায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

প্রতিটা i-র জন্য:
    s[i] কি s-এর অন্য কোনো জায়গায় আছে?
        না থাকলে → return i
return -1

কোথায় বেশি কাজ হচ্ছে

প্রতিটা অক্ষরের জন্য পুরো string scan = মোট O(n^2)। একই অক্ষরের count আমরা বারবার নতুন করে গুনছি — অথচ একবার সব গুনে রাখলে প্রতিটা lookup O(1) হয়ে যেত। সেই পুনরাবৃত্ত গোনাই অপচয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: count আর order আলাদা করে ফেলা যায়। প্রথমে সব count জোগাড় করো (order ভুলে), তারপর string-এর স্বাভাবিক order-এ হেঁটে প্রথম count-1 ধরো। এক problem-কে দুটো সহজ pass-এ ভাঙা।

আরও কম কাজে সমাধান

Pass 1: Counter(s) দিয়ে প্রতিটা অক্ষরের গণনা বানাও। Pass 2: index 0 থেকে শুরু করে প্রথম যে অক্ষরের count 1, তার index ফেরত দাও। দ্বিতীয় pass string-এর order-এ চলে বলে "প্রথম" আপনাআপনি ঠিক থাকে। কোনো count-1 না পেলে -1।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা অক্ষর কি unique" — এই প্রশ্ন প্রতিবার পুরো string স্ক্যান করে; বদলে আগে একবারে সব count জমাও, তারপর শুধু "count == 1?" জিজ্ঞেস করো। গোনা আর খোঁজাকে দুটো আলাদা pass-এ ভাগ করে দাও।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

"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

দুই 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

TypeScript

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 ছাড়া কিছু ফেরত দেওয়া যায় না।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• 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)

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

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