ভূমিকা

এই পোস্টে আমরা String সম্পর্কিত ৫টি মিডিয়াম লেভেলের কোডিং সমস্যা দেখব এবং Java ব্যবহার করে সেগুলোর বিস্তারিত সমাধান করব। প্রতিটি সমস্যার জন্য সমস্যার বিবরণ, চিন্তার পদ্ধতি এবং সম্পূর্ণ কোড দেওয়া হয়েছে।

সমস্যা ১: Longest Substring Without Repeating Characters

সমস্যার বিবরণ

একটি string s দেওয়া আছে। সেই string-এ কোনো character পুনরাবৃত্তি না হয়ে এমন সবচেয়ে দীর্ঘ substring-এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ:

• Input: s = "abcabcbb"
• Output: 3
• কারণ: "abc" হলো সবচেয়ে দীর্ঘ substring যেখানে কোনো character পুনরাবৃত্তি নেই

চিন্তার পদ্ধতি

Sliding Window এবং HashMap ব্যবহার করব। দুটি pointer left ও right রাখব। right pointer এগিয়ে যাবে এবং যখন duplicate character পাবো, তখন left pointer সরিয়ে দেব।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0;
        int left = 0;

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

            // যদি character আগে দেখা গিয়ে থাকে এবং window-এর ভেতরে থাকে
            if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
                left = charIndex.get(c) + 1; // left pointer সরিয়ে দাও
            }

            charIndex.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeating solution = new LongestSubstringWithoutRepeating();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); // Output: 3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb"));    // Output: 1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));   // Output: 3
    }
}

ধরা যাক s = "abcabcbb"। নিচে প্রতিটা right pointer-এর iteration-এ ঠিক কী ঘটছে তার trace:

right	char	আগের left	duplicate check	নতুন left	window	length	maxLength
0	a	0	map-এ নেই → না	0	"a"	1	1
1	b	0	map-এ নেই → না	0	"ab"	2	2
2	c	0	map-এ নেই → না	0	"abc"	3	3
3	a	0	map['a']=0, 0≥left(0) → হ্যাঁ	1	"bca"	3	3
4	b	1	map['b']=1, 1≥left(1) → হ্যাঁ	2	"cab"	3	3
5	c	2	map['c']=2, 2≥left(2) → হ্যাঁ	3	"abc"	3	3
6	b	3	map['b']=4, 4≥left(3) → হ্যাঁ	5	"cb"	2	3
7	b	5	map['b']=6, 6≥left(5) → হ্যাঁ	7	"b"	1	3

---

সমস্যা ২: Valid Anagram যাচাই করা

সমস্যার বিবরণ

দুটি string s এবং t দেওয়া আছে। যাচাই করতে হবে যে t হলো s-এর একটি anagram কিনা। Anagram মানে হলো একই character ব্যবহার করে ভিন্নভাবে সাজানো।

উদাহরণ:

• Input: s = "anagram", t = "nagaram"
• Output: true
• Input: s = "rat", t = "car"
• Output: false

চিন্তার পদ্ধতি

Character frequency count ব্যবহার করব। s-এর প্রতিটি character-এর count বাড়াব এবং t-এর প্রতিটি character-এর count কমাব। শেষে সব count যদি 0 হয়, তাহলে anagram।

সমাধান (Java)

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

        // 26টি lowercase letter-এর জন্য frequency array
        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++; // s-এর character count বাড়াই
            count[t.charAt(i) - 'a']--; // t-এর character count কমাই
        }

        // সব count 0 হলে anagram
        for (int c : count) {
            if (c != 0) return false;
        }

        return true;
    }

    public static void main(String[] args) {
        ValidAnagram solution = new ValidAnagram();
        System.out.println(solution.isAnagram("anagram", "nagaram")); // Output: true
        System.out.println(solution.isAnagram("rat", "car"));         // Output: false
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)

---

সমস্যা ৩: Palindrome String যাচাই করা (Longest Palindromic Substring)

সমস্যার বিবরণ

একটি string s দেওয়া আছে। সেই string-এর মধ্যে সবচেয়ে দীর্ঘ palindromic substring খুঁজে বের করতে হবে। Palindrome মানে হলো যে string সামনে থেকে এবং পেছন থেকে একই পড়া যায়।

উদাহরণ:

• Input: s = "babad"
• Output: "bab" অথবা "aba"
• Input: s = "cbbd"
• Output: "bb"

চিন্তার পদ্ধতি

Expand Around Center পদ্ধতি ব্যবহার করব। প্রতিটি character কে center ধরে বাম ও ডানে বিস্তার করব। Odd এবং even দৈর্ঘ্যের palindrome উভয়ই check করব।

সমাধান (Java)

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, maxLength = 1;

        for (int i = 0; i < s.length(); i++) {
            // Odd দৈর্ঘ্যের palindrome (single center)
            int len1 = expandAroundCenter(s, i, i);
            // Even দৈর্ঘ্যের palindrome (double center)
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);

            if (len > maxLength) {
                maxLength = len;
                start = i - (len - 1) / 2;
            }
        }

        return s.substring(start, start + maxLength);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring solution = new LongestPalindromicSubstring();
        System.out.println(solution.longestPalindrome("babad")); // Output: "bab"
        System.out.println(solution.longestPalindrome("cbbd"));  // Output: "bb"
        System.out.println(solution.longestPalindrome("racecar")); // Output: "racecar"
    }
}

সময় জটিলতা: O(n²) | স্থান জটিলতা: O(1)

---

সমস্যা ৪: String-এর সব Permutation খোঁজা (Permutation in String)

সমস্যার বিবরণ

দুটি string s1 এবং s2 দেওয়া আছে। যাচাই করতে হবে যে s2-এর মধ্যে s1-এর কোনো permutation আছে কিনা। অর্থাৎ s2-এ কোনো substring আছে কিনা যা s1-এর anagram।

উদাহরণ:

• Input: s1 = "ab", s2 = "eidbaooo"
• Output: true (কারণ s2-এ "ba" আছে যা "ab"-এর permutation)
• Input: s1 = "ab", s2 = "eidboaoo"
• Output: false

চিন্তার পদ্ধতি

Sliding Window ব্যবহার করব। s1-এর character frequency count রাখব এবং s2-এ s1.length() সমান window sliding করব। প্রতিটি window-এর frequency যদি s1-এর সাথে মিলে যায় তাহলে true।

সমাধান (Java)

public class PermutationInString {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] s1Count = new int[26];
        int[] windowCount = new int[26];

        // s1-এর frequency count
        for (char c : s1.toCharArray()) {
            s1Count[c - 'a']++;
        }

        int windowSize = s1.length();

        // প্রথম window initialize করি
        for (int i = 0; i < windowSize; i++) {
            windowCount[s2.charAt(i) - 'a']++;
        }

        if (matches(s1Count, windowCount)) return true;

        // Sliding window এগিয়ে যাই
        for (int i = windowSize; i < s2.length(); i++) {
            windowCount[s2.charAt(i) - 'a']++;           // নতুন character যোগ করি
            windowCount[s2.charAt(i - windowSize) - 'a']--; // পুরনো character সরাই

            if (matches(s1Count, windowCount)) return true;
        }

        return false;
    }

    private boolean matches(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        PermutationInString solution = new PermutationInString();
        System.out.println(solution.checkInclusion("ab", "eidbaooo")); // Output: true
        System.out.println(solution.checkInclusion("ab", "eidboaoo")); // Output: false
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)

---

সমস্যা ৫: String Encode এবং Decode (Group Anagrams)

সমস্যার বিবরণ

একটি string array strs দেওয়া আছে। সমস্ত anagram গুলোকে একসাথে group করতে হবে। যে string গুলো একে অপরের anagram, সেগুলো একই group-এ থাকবে।

উদাহরণ:

• Input: strs = ["eat","tea","tan","ate","nat","bat"]
• Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

চিন্তার পদ্ধতি

প্রতিটি string-কে sort করলে anagram গুলো একই sorted string পাবে। এই sorted string কে key হিসেবে HashMap-এ রাখব। একই key-এর সব string একই group-এ যাবে।

সমাধান (Java)

import java.util.*;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        // sorted string -> list of anagrams
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            // প্রতিটি string sort করে key বানাই
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            // একই key-এর list-এ string যোগ করি
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }

        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        GroupAnagrams solution = new GroupAnagrams();
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = solution.groupAnagrams(input);

        for (List<String> group : result) {
            System.out.println(group);
        }
        // Output:
        // [bat]
        // [tan, nat]
        // [eat, tea, ate]
    }
}

সময় জটিলতা: O(n * k log k) যেখানে k হলো সর্বোচ্চ string দৈর্ঘ্য | স্থান জটিলতা: O(n * k)

---

সারসংক্ষেপ

সমস্যা	পদ্ধতি	সময় জটিলতা	স্থান জটিলতা
Longest Substring Without Repeating	Sliding Window + HashMap	O(n)	O(min(m,n))
Valid Anagram	Frequency Count Array	O(n)	O(1)
Longest Palindromic Substring	Expand Around Center	O(n²)	O(1)
Permutation in String	Sliding Window	O(n)	O(1)
Group Anagrams	Sorting + HashMap	O(n·k log k)	O(n·k)

এই সমস্যাগুলো interview-এ খুবই সাধারণ। Sliding Window, HashMap, এবং Two Pointer-এর মতো pattern গুলো ভালোভাবে বুঝলে String-এর বেশিরভাগ সমস্যা সমাধান করা সম্ভব।