String Advanced Problems

স্ট্রিং-এর অ্যাডভান্সড প্রবলেমগুলো ইন্টারভিউতে খুব বেশি জিজ্ঞাসা করা হয়। এখানে আমরা কিছু জনপ্রিয় এবং জটিল প্রবলেম নিয়ে আলোচনা করব।

১. লংগেস্ট কমন প্রিফিক্স (Longest Common Prefix)

একাধিক স্ট্রিং-এর মধ্যে শুরু থেকে যে অংশটুকু কমন থাকে তাকেই Longest Common Prefix বলে।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. অ্যারের প্রথম স্ট্রিংটিকে লজিক্যাল prefix হিসেবে ধরে নিন।
2. পরবর্তী প্রতিটি স্ট্রিং-এর সাথে এই prefix-টি মিলিয়ে দেখুন।
3. যদি না মিলে, তবে prefix-এর শেষ থেকে একটি করে ক্যারেক্টার বাদ দিতে থাকুন যতক্ষণ না ম্যাচ পাওয়া যায়।
4. যদি prefix এম্পটি হয়ে যায়, তবে কমন কোনো অংশ নেই।
5. সব স্ট্রিং চেক শেষে যা অবশিষ্ট থাকবে, সেটিই লংগেস্ট কমন প্রিফিক্স।

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

def longestCommonPrefix(strs):
    if not strs: return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix: return ""
    return prefix

২. লংগেস্ট প্যালিনড্রোমিক সাবস্ট্রিং (Longest Palindromic Substring)

একটি স্ট্রিং থেকে সবচেয়ে বড় যে সাবস্ট্রিংটি প্যালিনড্রোম (Palindrome), সেটি খুঁজে বের করা। এটি "Expand Around Center" পদ্ধতি দিয়ে খুব সহজে সমাধান করা যায়।

Time Complexity: $O(n^2)$

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. স্ট্রিং-এর প্রতিটি ক্যারেক্টারকে একটি সম্ভাব্য কেন্দ্র (Center) হিসেবে ধরুন।
2. প্যালিনড্রোম দুই ধরণের হতে পারে: বিজোড় দৈর্ঘ্যের (Center এ একটি ক্যারেক্টার) এবং জোড় দৈর্ঘ্যের (Center এ দুটি ক্যারেক্টার)।
3. কেন্দ্র থেকে বামে এবং ডানে যতক্ষণ ক্যারেক্টার মিলবে, ততক্ষণ সাব-স্ট্রিংটি বড় করুন।
4. প্রতিটি ধাপে পাওয়া সাব-স্ট্রিং এর সাথে বর্তমান সর্বোচ্চ দৈর্ঘ্যের সাব-স্ট্রিং তুলনা করে স্টোর করুন।

def longestPalindrome(s):
    res = ""
    for i in range(len(s)):
        # Odd length
        tmp = expand(s, i, i)
        if len(tmp) > len(res): res = tmp
        # Even length
        tmp = expand(s, i, i + 1)
        if len(tmp) > len(res): res = tmp
    return res

def expand(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l+1:r]

৩. ওয়ার্ড ব্রেক প্রবলেম (Word Break Problem)

চেক করা যে একটি স্ট্রিং-কে কি ডিকশনারিতে থাকা শব্দগুলোর মাধ্যমে ছোট ছোট ভাগে ভাগ করা সম্ভব কি না। এটি ডাইনামিক প্রোগ্রামিং (DP) ব্যবহার করে সমাধান করা হয়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি dp অ্যারে নিন যার সাইজ হবে স্ট্রিংয়ের দৈর্ঘ্যের চেয়ে ১ বেশি। dp[0] কে true মার্ক করুন।
2. দুটি লুপ চালান: i (১ থেকে n পর্যন্ত) এবং j (০ থেকে i পর্যন্ত)।
3. যদি dp[j] সত্য হয় এবং s[j:i] ডিকশনারিতে থাকে, তবে dp[i] কে true মার্ক করুন।
4. লুপ শেষে dp[n] এর ভ্যালু রিটার্ন করুন।

Implementation

# Python Word Break
def word_break(s, wordDict):
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                break
    return dp[len(s)]

// Java Word Break
public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

৪. মিনিমাম উইন্ডো সাবস্ট্রিং (Minimum Window Substring)

একটি স্ট্রিংয়ের মধ্যে ক্ষুদ্রতম সেই সাবস্ট্রিংটি খুঁজে বের করা যার মধ্যে অন্য একটি স্ট্রিংয়ের সব ক্যারেক্টার বিদ্যমান। এটি "Sliding Window" টেকনিকের একটি দারুণ উদাহরণ।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. টার্গেট স্ট্রিং t এর ক্যারেক্টার ফ্রিকোয়েন্সি ম্যাপ তৈরি করুন।
2. স্ট্রিং s এর ওপর স্লাইডিং উইন্ডো (from এবং to) ব্যবহার করুন।
3. উইন্ডোর ডান পাশের পয়েন্টার to স্লাইড করুন যতক্ষণ না সব টার্গেট ক্যারেক্টার উইন্ডোতে আসে।
4. যখন সব ক্যারেক্টার পাওয়া যাবে, তখন বাম পাশের পয়েন্টার from কমানোর চেষ্টা করুন ছোট সাব-স্ট্রিং পাওয়ার জন্য।
5. প্রতিটি সঠিক উইন্ডোর সাইজ চেক করে মিনিমাম ভ্যালুটি সেভ করুন।

public String minWindow(String s, String t) {
    int[] count = new int[128];
    for (char c : t.toCharArray()) count[c]++;
    int from = 0, to = 0, minLen = Integer.MAX_VALUE, cnt = t.length(), start = 0;
    while (to < s.length()) {
        if (count[s.charAt(to++)]-- > 0) cnt--;
        while (cnt == 0) {
            if (to - from < minLen) {
                minLen = to - from;
                start = from;
            }
            if (count[s.charAt(from++)]++ == 0) cnt++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

৫. লংগেস্ট সাবস্ট্রিং উইদাউট রিপিটিং (Longest Substring Without Repeating)

এমন একটি সাবস্ট্রিং খুঁজে বের করা যেখানে কোনো ক্যারেক্টার দুইবার নেই। এটি স্লাইডিং উইন্ডো এবং হ্যাশ ম্যাপ দিয়ে সমাধান করা হয়।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. দুটি পয়েন্টার ব্যবহার করুন: left এবং right।
2. right পয়েন্টার দিয়ে সামনে এগিয়ে যান এবং ক্যারেক্টারের অবস্থান হ্যাশ ম্যাপে সেভ করুন।
3. যদি কোনো ক্যারেক্টার রিপিট হয় এবং তার শেষ অবস্থান left-এর পরে থাকে, তবে left কে সেই পজিশনের পরে সরিয়ে নিন।
4. প্রতিটি ধাপে উইন্ডোর দৈর্ঘ্য (right - left + 1) ক্যালকুলেট করে ম্যাক্সিমাম ভ্যালু আপডেট করুন।

def lengthOfLongestSubstring(s):
    char_map = {}
    left = max_len = 0
    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)
        char_map[s[right]] = right
        max_len = max(max_len, right - left + 1)
    return max_len

৬. স্ট্রিং কমপ্রেশন (String Compression)

স্ট্রিংকে কম্প্রেস করা যেমন: "aaabb" -> "a3b2"। যদি কম্প্রেসড স্ট্রিং মূল স্ট্রিং থেকে বড় হয় তবে মূল স্ট্রিং রিটার্ন করতে হবে।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. স্ট্রিংটি লুপ চালিয়ে ট্রাভার্স করুন।
2. পাশাপাশি দুটি ক্যারেক্টার চেক করুন। যদি একই হয়, তবে count বাড়ান।
3. ভিন্ন ক্যারেক্টার পেলে, বর্তমান ক্যারেক্টার এবং তার কাউন্ট (যদি ১-এর বেশি হয়) রেজাল্টে যোগ করুন।
4. লুপ শেষে কম্প্রেসড স্ট্রিং এবং মূল স্ট্রিং-এর মধ্যে যেটি ছোট সেটি রিটার্ন করুন।

Implementation

# Python String Compression
def compress_string(s):
    if not s: return ""
    res = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            res.append(s[i-1])
            if count > 1:
                res.append(str(count))
            count = 1
    res.append(s[-1])
    if count > 1:
        res.append(str(count))

    compressed_str = "".join(res)
    return compressed_str if len(compressed_str) < len(s) else s

// Java String Compression
public String compress(String s) {
    if (s == null || s.isEmpty()) return s;
    StringBuilder sb = new StringBuilder();
    int count = 1;
    for (int i = 0; i < s.length(); i++) {
        if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
            count++;
        } else {
            sb.append(s.charAt(i));
            if (count > 1) {
                sb.append(count);
            }
            count = 1;
        }
    }
    String compressedString = sb.toString();
    return compressedString.length() < s.length() ? compressedString : s;
}

৭. ওয়াইল্ডকার্ড ম্যাচিং (Wildcard Matching - Intro)

স্ট্রিংয়ের সাথে প্যাটার্ন ম্যাচিং যেখানে '?' এবং '*' এর মত স্পেশাল ক্যারেক্টার থাকে। এটি খুব জনপ্রিয় একটি অ্যাডভান্সড ডাইনামিক প্রোগ্রামিং প্রবলেম।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি 2D dp টেবিল তৈরি করুন যেখানে dp[i][j] মানে s[0..i-1] এবং p[0..j-1] ম্যাচ করে কি না।
2. dp[0][0] = True মার্ক করুন (খালি স্ট্রিং এবং খালি প্যাটার্ন)।
3. প্যাটার্নে * থাকলে সেগুলোর বেস কেস হ্যান্ডেল করুন।
4. লুপ চালিয়ে প্রতিটি ক্যারেক্টার চেক করুন:
   • যদি ক্যারেক্টার মিলে বা ? হয়, তবে আগের ডায়াগোনাল ভ্যালু নিন।
   • যদি * হয়, তবে হয় * কে খালি স্ট্রিং হিসেবে ধরুন অথবা কোনো চরিত্রের সাথে মিলিয়ে নিন।
5. শেষে dp[len(s)][len(p)] রিটার্ন করুন।

Implementation

# Python Wildcard Matching
def is_match(s, p):
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True
    for j in range(1, len(p) + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j-1] == '?' or s[i-1] == p[j-1]:
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]
    return dp[len(s)][len(p)]

// Java Wildcard Matching
public boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int j = 1; j <= p.length(); j++) {
        if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p.charAt(j - 1) == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    }
    return dp[s.length()][p.length()];
}