৫টি সহজ String কোডিং প্রবলেম ও সমাধান (Java)

সিরিজের চতুর্থ ফাইল — Tree, BFS/DFS, Linked List-এর পর এবার String। এখানকার মূল প্যাটার্নগুলো: two pointer, frequency count (HashMap/array), sliding window। Longest Substring Without Repeating Characters আগেই করেছেন — এই ৫টি তার ভিত মজবুত করবে।

প্রবলেম ১: Valid Palindrome (LeetCode 125)

প্রশ্ন: একটি string palindrome কিনা যাচাই করুন — শুধু letter ও digit ধরে, case উপেক্ষা করে। যেমন "A man, a plan, a canal: Panama" → true।

চিন্তার ধাপ: Two pointer — একটি বাম প্রান্ত থেকে, একটি ডান প্রান্ত থেকে। যে চরিত্র alphanumeric নয়, তাকে টপকে যান। দুই প্রান্তের চরিত্র (lowercase করে) না মিললেই false। নতুন string বানিয়ে reverse করার দরকার নেই — এতে O(n) বাড়তি space বাঁচে।

সমাধান:

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        // alphanumeric নয় এমন চরিত্র টপকে যান
        while (left < right && !Character.isLetterOrDigit(s.charAt(left)))  left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

        if (Character.toLowerCase(s.charAt(left))
                != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: ভেতরের while-গুলোতেও left < right চেকটি জরুরি — নইলে ".,,"-এর মতো input-এ pointer সীমা ছাড়িয়ে যায়। আর সহজ সমাধানটাও বলুন ("clean করে StringBuilder.reverse() দিয়ে তুলনা") — তারপর বলুন কেন two-pointer ভালো: বাড়তি O(n) space নেই। বিকল্প জেনে সচেতনভাবে বাছাই করাই senior signal।

প্রবলেম ২: Valid Anagram (LeetCode 242)

প্রশ্ন: দুটি string পরস্পরের anagram কিনা — অর্থাৎ একই অক্ষর একই সংখ্যকবার আছে কিনা। "listen" ও "silent" → true।

চিন্তার ধাপ: Frequency count — String প্রবলেমের সবচেয়ে বহুল ব্যবহৃত অস্ত্র। প্রথম string-এর প্রতিটি অক্ষরে count বাড়ান, দ্বিতীয়টির প্রতিটিতে কমান। শেষে সব count শূন্য হলে anagram। ছোট হাতের a-z হলে HashMap-এর বদলে int[26] — দ্রুত ও সহজ।

সমাধান:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }

    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Complexity: Time O(n), Space O(1) — array-র আকার নির্দিষ্ট (26)।

ইন্টারভিউ টিপ: প্রথম লাইনের length চেকটি ছোট কিন্তু গুরুত্বপূর্ণ optimization। সহজ বিকল্প — দুটোকেই sort করে তুলনা, O(n log n) — বলুন, তারপর O(n) সমাধান দিন। নিশ্চিত follow-up: "Unicode হলে?" → int[26] চলবে না, HashMap<Character, Integer> (বা code point ধরে Map<Integer, Integer>) লাগবে — এই এক লাইন জানা থাকলেই যথেষ্ট।

প্রবলেম ৩: First Unique Character (LeetCode 387)

প্রশ্ন: String-এর প্রথম যে চরিত্রটি মাত্র একবার এসেছে, তার index দিন। না থাকলে -1। "leetcode" → 0 (l), "loveleetcode" → 2 (v)।

চিন্তার ধাপ: দুই pass: প্রথম pass-এ সব চরিত্রের frequency গুনুন, দ্বিতীয় pass-এ বাম থেকে প্রথম যার count == 1, তার index-ই উত্তর। এক pass-এ করার লোভ সামলান — দুই pass-ও O(n)-ই, এবং অনেক পরিষ্কার।

সমাধান:

public int firstUniqChar(String s) {
    int[] count = new int[26];

    // Pass ১: frequency গণনা
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    // Pass ২: প্রথম unique খুঁজুন
    for (int i = 0; i < s.length(); i++) {
        if (count[s.charAt(i) - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: "দুই pass কি খারাপ না?" — না; O(2n) = O(n)। বরং এক-pass-এর জটিল সমাধান বেশি bug-প্রবণ। সরলতা defend করতে পারাও দক্ষতা। Follow-up হতে পারে: "stream of characters হলে?" → তখন LinkedHashMap বা queue দিয়ে order-preserving গণনা — ডিজাইন আলোচনায় গড়ায়।

প্রবলেম ৪: Longest Common Prefix (LeetCode 14)

প্রশ্ন: একগুচ্ছ string-এর দীর্ঘতম সাধারণ prefix বের করুন। ["flower","flow","flight"] → "fl"।

চিন্তার ধাপ: Vertical scanning — প্রথম string-এর প্রতিটি চরিত্র ধরে বাকি সবার একই position-এ মিলছে কিনা দেখুন। যেখানে প্রথম গরমিল (বা কোনো string শেষ), সেখানেই থামুন।

সমাধান:

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    for (int i = 0; i < strs[0].length(); i++) {   // প্রথম string-এর column ধরে
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {     // বাকি সব string-এ
            if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);     // গরমিল → এ পর্যন্তই prefix
            }
        }
    }
    return strs[0];  // প্রথম string-টাই পুরো prefix
}

Complexity: Time O(S) — S = সব string-এর মোট চরিত্র সংখ্যা। Space O(1)।

ইন্টারভিউ টিপ: i >= strs[j].length() চেকটি আগে — নইলে ছোট string-এ ("flow" শেষ হয়ে গেলে) StringIndexOutOfBounds। Follow-up: "লক্ষ লক্ষ string, বারবার এই query হলে?" → Trie — যেটি আপনি আগেই এই সিরিজে বানিয়েছেন! Trie-তে root থেকে যতক্ষণ একটিই child ও end-of-word নেই, ততক্ষণ নেমে গেলেই common prefix। দুটি প্রবলেম জুড়তে পারা দারুণ দেখায়।

প্রবলেম ৫: Longest Substring Without Repeating Characters (LeetCode 3) — Sliding Window রিভিশন

প্রশ্ন: পুনরাবৃত্তিহীন দীর্ঘতম substring-এর দৈর্ঘ্য। "abcabcbb" → 3 ("abc")।

চিন্তার ধাপ: আপনার আগেই করা প্রবলেম — এবার প্যাটার্নটি ভাষায় গেঁথে নিন। Sliding window: ডান pointer এগিয়ে window বড় করুন; duplicate ঢুকলেই বাম pointer টেনে window বৈধ করুন। int[256]-এ প্রতিটি চরিত্রের সর্বশেষ দেখা index রাখলে বাম pointer এক লাফে সঠিক জায়গায় চলে যায় — এক এক ঘর হেঁটে নয়।

সমাধান:

public int lengthOfLongestSubstring(String s) {
    int[] lastIndex = new int[256];
    Arrays.fill(lastIndex, -1);

    int maxLen = 0;
    int left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (lastIndex[c] >= left) {       // duplicate টি বর্তমান window-র ভেতরে
            left = lastIndex[c] + 1;      // বাম pointer এক লাফে duplicate-এর পরে
        }
        lastIndex[c] = right;
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Complexity: Time O(n) — এক pass। Space O(1) — নির্দিষ্ট আকারের array।

ইন্টারভিউ টিপ: সূক্ষ্মতম অংশ — lastIndex[c] >= left (শুধু != -1 নয়)। Duplicate-টি window-র বাইরে (বামে) থাকলে সেটি duplicate-ই নয়; left কমে পেছনে চলে গেলে ভুল উত্তর। এই এক তুলনাই এই প্রবলেমের আসল পরীক্ষা। এই টেমপ্লেট আয়ত্তে থাকলে Minimum Window Substring (76), Longest Repeating Character Replacement (424) — সবই একই ছাঁচে।

String প্যাটার্ন — মনে রাখুন

আর তিনটি Java-নির্দিষ্ট সোনার নিয়ম:

১. == নয়, .equals() — string content তুলনায়। == reference তুলনা করে; ইন্টারভিউতে এই ভুল খুব চোখে লাগে। ২. Loop-এ string জোড়া দিতে StringBuilder — s += c প্রতিবার নতুন object বানায়, O(n²) হয়ে যায়। String immutable — এটাই কারণ, বলতে পারা চাই। ৩. charAt(i) - 'a' — চরিত্র থেকে array index-এ যাওয়ার idiom; frequency array-র প্রাণ।

পরবর্তী ধাপ: medium-এ যান — Group Anagrams (49, frequency count-এর প্রসারণ), Longest Palindromic Substring (5, expand-from-center), Minimum Window Substring (76, sliding window-র চূড়া), String to Integer/atoi (8, edge case-এর রাজা)।