Practice Projects

Construct K Palindrome Strings

Problem Statement

Ek string s aur ek integer k diye gaye hain. Aapko batana hai ki kya aap s ke saare characters use karke k palindrome strings bana sakte ho ya nahi.

Palindrome: Palindrome wo string hoti hai jo reverse hone par bhi same rahe. Jaise “anna”, “madam”.

Example 1:

  • Input: s = "annabelle", k = 2

  • Output: true

  • Explanation: Aap “annabelle” ke characters use karke do palindromes bana sakte ho. Kuch possible constructions hain “anna” + “elble”, “anbna” + “elle”, “anellena” + “b”.

Example 2:

  • Input: s = "leetcode", k = 3

  • Output: false

  • Explanation: “leetcode” ke characters use karke 3 palindromes banana impossible hai.

Example 3:

  • Input: s = "true", k = 4

  • Output: true

  • Explanation: Har character ko alag alag string mein rakh kar 4 palindromes ban sakte hain.

Constraints:

  • 1 <= <= 105

  • s mein sirf lowercase English letters hote hain.

  • 1 <= k <= 105

Logic: Palindrome banane ke liye, agar odd frequency wale characters ki sankhya k se zyada hai, toh k palindrome nahi ban sakte. Kyunki palindrome mein odd frequency ke character sirf ek bar center mein ho sakte hain.

Practice Projects

Construct K Palindrome Strings

Har ek character ki frequency ko dekho.

Palindrome banane ke liye har character ki ek jodi honi chahiye (do-do baar aana chahiye).

Jo character odd frequency mein hain, wo sirf ek palindrome ke center mein aa sakte hain.

Agar humare paas k palindromes banane hain, toh minimum odd frequency wale characters ki sankhya k se kam ya barabar honi chahiye.

Agar total odd frequency wale characters k se zyada hain, toh itne palindromes banana mumkin nahi hai.

Yeh intuition iss problem ka hai. Agar odd frequency wale characters k se kam hain, toh k palindrome strings banane mumkin hain, warna nahi.

Intuition

Sort the String: Sabse pehle, string ko sort kar do, taaki identical characters ek saath aa jayein. Jaise "annabelle" ko sort karne par milega "aaebellnn".

Count Odd Frequencies: Sorted string mein, har character ki frequency count karo aur dekho kitne characters ki frequency odd (asan sankhya) hai. Odd frequency wale characters woh hain jinka palindrome banane ke liye central position mein aana zaroori hai.

Check Feasibility: Ye ensure karo ki odd frequency wale characters ki total sankhya k ke barabar ya kam ho. Agar odd frequencies ≤ k hai, toh hum k palindrome bana sakte hain. Warna, nahi bana sakte.

Approach

Time Complexity:

  • O(n log n): String ko sort karna padta hai, aur sorting ka time complexity hota hai O(n log n), jahan n string ki length hai.

Space Complexity:

  • O(n): Sorted characters ko store karne ke liye extra space lagti hai, jo ki original string ke size ke barabar hoti hai, yaani O(n).

Solution

				
					var canConstruct = function(s, k) {
    // Agar string ki length k se choti hai, toh return false
    if (s.length < k) return false;

    // String ko characters mein convert karo aur sort kar do
    let chars = [...s].sort();
    let oddCount = 0;

    // Har character ki frequency count karte hain
    for (let i = 0; i < chars.length; ) {
        let current = chars[i];
        let count = 0;
        while (i < chars.length && chars[i] === current) {
            count++;
            i++;
        }
        // Agar count odd hai toh oddCount badhao
        if (count % 2 !== 0) oddCount++;
    }

    // Agar oddCount k se kam ya barabar hai toh return true, warna false
    return oddCount <= k;
};

  • Initial Check: Pehle, check karo ki string s ki length k se kam hai ya nahi. Agar kam hai, toh aap k palindromes nahi bana sakte, isliye false return karo.

  • String Sorting: String s ko sort karo. Isse similar characters ek saath aa jate hain, jisse frequency count karna aasan ho jata hai.

  • Count Odd Frequencies: Har character ki frequency count karo. Yeh dekho ki kaunse characters odd (asan) frequency mein hain. Palindrome banane ke liye central position mein odd frequency wale characters honi chahiye.

  • Check Feasibility: Last mein, dekho ki odd frequency wale characters ki sankhya k se kam ya barabar hai ya nahi. Agar hai, toh aap k palindromes bana sakte hain, isliye true return karo. Agar zyada hai, toh false return karo.

Solution

				
					class Solution {
public:
    bool canConstruct(string s, int k) {
        // Agar string ki length k se kam hai, toh return false
        if (s.length() < k) return false;

        // String ko sort kar do taaki similar characters ek saath ho jayein
        sort(s.begin(), s.end());
        int oddCount = 0;

        // Har character ki frequency count karte hain
        for (int i = 0; i < s.length(); ) {
            char current = s[i];
            int count = 0;
            // Jab tak current character same hai, count ko badhao
            while (i < s.length() && s[i] == current) {
                count++;
                i++;
            }
            // Agar count odd (asan) hai toh oddCount ko badhao
            if (count % 2 != 0) oddCount++;
        }

        // Agar oddCount k se kam ya barabar hai toh true return karo, warna false
        return oddCount <= k;
    }
};

 

  • Initial Check: Pehle check karte hain ki string s ki length k se kam hai ya nahi. Agar s ki length k se kam hai, toh false return karte hain, kyunki itne palindromes banana possible nahi hai.

  • Sort the String: String s ko sort karte hain taaki same characters ek saath aa jayein. Yeh sorting asaan banati hai similar characters ki frequency count karna.

  • Count Odd Frequencies: Sorted string mein har character ki frequency count karte hain. Jab tak ek jaisa character milta rahe, uska count badhate hain. Agar count odd (asan) hai, toh odd frequency wale characters ki sankhya ko badhate hain.

  • Check Feasibility: Last mein yeh check karte hain ki odd frequency wale characters ki sankhya k se kam ya barabar hai ya nahi. Agar odd frequency wale characters ki sankhya k se kam ya barabar hai, toh true return karte hain, warna false.