একটি স্ট্রিং-এর প্রথম ইউনিক অক্ষর খুঁজে বের করা

Introduction

আজকে আমরা একটি খুবই পপুলার ইন্টারভিউ সমস্যা নিয়ে কথা বলব, যার নাম হলো "First Unique Character in a String"। এটি লিটকোড (LeetCode)-এর ৩৮৭ নম্বর সমস্যা। সহজ কথায় বলতে গেলে, আপনাকে একটা লেখা বা স্ট্রিং দেওয়া হবে, আর আপনাকে খুঁজে বের করতে হবে সেই লেখার মধ্যে প্রথম কোন অক্ষরটি মাত্র একবার আছে (অর্থাৎ রিপিট হয়নি)। যদি এমন কোনো অক্ষর থাকে, তবে তার পজিশন বা ইনডেক্স বলতে হবে, আর না থাকলে -১ রিটার্ন করতে হবে।

---

১. সমস্যার মূল ধারণা (Problem Understanding)

ভিডিও রেফারেন্স: [00:04]

এই সমস্যাটিকে অনেক সময় "First Non-repeating Character in a Stream" বলা হয়। নাম আলাদা হলেও সমাধান কিন্তু একই।

ধরা যাক, আমাদের কাছে একটি স্ট্রিং আছে: "leetcode"

• এখানে 'l' একবারই আছে। তাই এর ইনডেক্স 0 হবে আমাদের উত্তর। আবার ধরুন: "loveleetcode"

• 'l' দুইবার আছে (রিপিট)।

• 'o' দুইবার আছে (রিপিট)।

• 'v' মাত্র একবার আছে এবং এটিই প্রথম ইউনিক অক্ষর। এর ইনডেক্স 2 হলো উত্তর।

সহজ ভাষায় ব্যাখ্যা:

• ইউনিক (Unique): যা দ্বিতীয়বার আর আসেনি।

• ইনডেক্স (Index): কম্পিউটার বিজ্ঞানে কোনো কিছুর অবস্থান ০ থেকে গোনা শুরু হয়। যেমন "ABC" তে A এর ইনডেক্স ০, B এর ১।

---

২. সমাধানের জন্য প্রয়োজনীয় ডেটা স্ট্রাকচার (Data Structures Used)

ভিডিও রেফারেন্স: [01:50]

এই সমস্যাটি সমাধান করতে আমরা দুটি জিনিস ব্যবহার করব:

1. Unordered Map (Hashing): এটি প্রতিটি অক্ষর কতবার এসেছে তার হিসাব (Frequency) রাখতে সাহায্য করবে।

2. Queue: এটি প্রথম কোন অক্ষরটি এসেছে তার সিরিয়াল মনে রাখতে সাহায্য করবে (FIFO - First In First Out)।

সহজ ভাষায় ব্যাখ্যা:

• Unordered Map: মনে করুন একটি ডায়েরি যেখানে আপনি লিখছেন 'A' এসেছে ২ বার, 'B' এসেছে ১ বার।

• Queue: এটি একটি লাইনের মতো। যে আগে লাইনে দাঁড়াবে, সে আগে সেবা পাবে।

---

৩. কাজের ধাপ বা লজিক (The Logic/Approach)

ভিডিও রেফারেন্স: [04:52]

আমরা স্ট্রিংটি এক মাথা থেকে অন্য মাথা পর্যন্ত চেক করব:

• ধাপ ১: যদি কোনো নতুন অক্ষর পাই, সেটি ম্যাপে যোগ করব এবং কিউ (Queue)-তে তার ইনডেক্স রাখব।

• ধাপ ২: যদি দেখি ওই অক্ষর আগে থেকেই ম্যাপে আছে, তবে শুধু তার কাউন্ট বাড়িয়ে দেব।

• ধাপ ৩: কিউ-এর সামনে (Front) যে আছে, সে ইউনিক কি না চেক করব। যদি দেখি সে রিপিট হয়েছে (কাউন্ট ১-এর বেশি), তাকে কিউ থেকে বের করে দেব।

• ধাপ ৪: শেষে কিউ-এর সামনে যে থাকবে, সেই আমাদের কাঙ্ক্ষিত প্রথম ইউনিক অক্ষর।

---

৪. কোডিং সমাধান (C++ Code Snippet)

ভিডিও রেফারেন্স: [10:36]

নিচে সি-প্লাস-প্লাস (C++) ভাষায় কোডটি দেওয়া হলো:

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;

int firstUniqChar(string s) {
    unordered_map<char, int> m; // অক্ষরের সংখ্যা রাখার জন্য
    queue<int> q; // ইউনিক অক্ষরের ইনডেক্স রাখার জন্য

    for (int i = 0; i < s.length(); i++) {
        char ch = s[i];
        
        // ম্যাপে অক্ষরের সংখ্যা বাড়ানো
        m[ch]++;
        
        // কিউ-তে ইনডেক্স রাখা
        q.push(i);

        // কিউ-এর সামনের অক্ষরটি যদি রিপিট হয়, তাকে বের করে দাও
        while (!q.empty() && m[s[q.front()]] > 1) {
            q.pop();
        }
    }

    // যদি কিউ খালি না হয়, তবে সামনের ইনডেক্সটিই উত্তর
    return q.empty() ? -1 : q.front();
} 

কোডের ব্যাখ্যা:

• m[ch]++: এই লাইনটি ম্যাপে বলে দিচ্ছে এই অক্ষরটি কতবার দেখা গেল।

• q.push(i): এটি লাইনে ইনডেক্স যোগ করছে।

• while লুপ: এটি চেক করছে লাইনের একদম শুরুতে থাকা অক্ষরটি কি একাধিকবার এসেছে? যদি হ্যাঁ হয়, তবে তাকে সরিয়ে দাও কারণ সে আর ইউনিক নেই।

---

৫. বিশ্লেষণ ও আমার মতামত (Analysis & Thinking)

সময় ও জায়গার হিসাব (Complexity Analysis):

• Time Complexity: O(n) - কারণ আমরা পুরো স্ট্রিং একবার মাত্র ঘুরছি। লিনিয়ার টাইম হওয়ার কারণে এটি খুব দ্রুত কাজ করে। [12:16]

• Space Complexity: O(n) - আমরা বাড়তি ম্যাপ এবং কিউ ব্যবহার করছি ডেটা রাখার জন্য। [13:02]

আমার চিন্তাভাবনা ও বিকল্প: ভিডিওটিতে স্রদ্ধা খাপরা (Shradha Khapra) কিউ ব্যবহার করে খুব সুন্দরভাবে সমস্যার সমাধান দেখিয়েছেন। তবে এই সমস্যাটি কিউ ছাড়াও আরও সহজভাবে করা যায়। আমরা প্রথমে একবার লুপ চালিয়ে সবার কাউন্ট বের করে নিতে পারি, এরপর দ্বিতীয়বার লুপ চালিয়ে দেখতে পারি কার কাউন্ট ১। সেটি আরও কম মেমোরি খরচ করতে পারে (Space Complexity O(26) বা ধ্রুবক হবে যদি শুধু ইংরেজি ছোট হাতের অক্ষর থাকে)।

বাস্তব জীবনের উদাহরণ: এই লজিকটি বিভিন্ন সার্চ ইঞ্জিন বা টেক্সট এডিটর ফিল্টারে ব্যবহার করা হয় যেখানে দ্রুত অদ্বিতীয় কোনো প্যাটার্ন খুঁজে বের করার প্রয়োজন পড়ে। বিগিনারদের জন্য এটি ডেটা স্ট্রাকচারের সমন্বয় শেখার একটি চমৎকার উদাহরণ।

[

L80. First Unique Character in String | Easy - Leetcode387

Shradha Khapra · 38K views

](http://www.youtube.com/watch?v=sqyCBvEQN9c)