Practice Projects

Unique Length-3 Palindromic Subsequences

Problem Statement

Given Problem: Ek string s di gayi hai, hamein pata karna hai ki aisi kitni unique palindromes hain jo length 3 ki hain aur subsequence ke roop mein s ka hissa hain.

Yeh dhyaan mein rakho ki agar ek hi subsequence ko multiple tarikon se paaya jaye, toh usse ek hi baar count kiya jayega.

Palindrome woh string hoti hai jo dono taraf se padhne par same hoti hai. Misan: “aad”[forward] == “daa”[backward]

Subsequence ek nayi string hoti hai jo original string se kuch characters (koi bhi 0 ya zyada) hata kar badhdocha order badale bina banayi gayi hoti hai.

Misaal ke taur par, “ace” ek subsequence hai “abcde” ka.

Example dekhte hain:

Example 1: Input: s = “aabca” Output: 3 Explanation: 3 palindromic subsequences jo length 3 ki hain:

  • “aba” (“aabca”)

  • “aaa” (“aabca”)

  • “aca” (“aabca”)

Example 2: Input: s = “adc” Output: 0 Explanation: “adc” mein koi bhi palindromic subsequences nahi hain.

Example 3: Input: s = “bbcbaba” Output: 4 Explanation: 4 palindromic subsequences =>

  • “bbb” (“bbcbaba”)

  • “bcb” (“bbcbaba”)

  • “bab” (“bbcbaba”)

  • “aba” (“bbcbaba”)

Constraints:

  • String s ka length minimum 3 aur maximum 105.

  • s sirf lowercase English letters se bana hai.

Practice Projects

Unique Length-3 Palindromic Subsequences

Yahan hamein 3 length wale palindromic subsequences dhundne hain jo given string mein hain. Tumhara approach yeh hai:
Characters ke first aur last occurrence ko dhoondo: Har character ka sabse pehla aur sabse aakhri occurrence identify karo.
Unique characters ko gino: Har character ke first aur last occurrence ke beech kisne unique characters ko count karo.
Middle character's subsequences: Yeh count humein batayega ki kitne unique palindromic subsequences ban sakte hain jahan middle character wohi hai.
Is process ko string ke har character ke liye repeat karenge aur sab count add karke final answer mil jaayega.

Intuition

Count variable initialize karo: Sabse pehle ek count variable ko 0 se initialize karoge jo final answer store karega.
Characters pe iterate karna: Ab har character ko string mein iterate karenge aur uska pehla aur aakhri occurrence dhoondhenge.
Unique characters ke beech: Pehla aur aakhri occurrence ke beech kitne unique characters hain, yeh ginte hain.
Count add karna: Har character ke liye yeh unique characters ka count final count variable mein add karte jayenge.
Return final answer: Jab sab characters pe iteration poora ho jaye, to final count variable ko return kar denge, jo humara answer hai.
Summarizing kaise karte hain kuchaise dekho:
- Tum string mein sab characters ko check karte ho,
- Unka pehla aur aakhri occurrence note karte ho,
- Beech mein unique characters ginte ho aur unko add kar dete ho count variable mein.

- Aur bas, aakhir mein apne count ko return kar dete ho jo humare solution ka answer hai.

Approach

Time Complexity:

  • Tumhara solution O(N) hai, jahaan N string ki length hai. Matlab har character ko ek baar dekhna padega, phir uske first aur last occurrence ke beech unique characters count karenge. Is poore process ko N times chalana parega, isliye time complexity O(N) hai.

Space Complexity:

  • Tumhara solution O(1) space complexity ka hai, kyunki additional space constant hai. Hum bas ek count variable aur kuch pointers use kar rahe hain, jo constant space kehlate hain. Bina kisi additional space ke (like arrays or hashmaps) ye solution chal raha hai.

Solution

				
					/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function(s) {
    // Final count store karne ke liye variable initialize karo
    let count = 0;

    // 'a' se 'z' ke liye loop chalayenge (0 to 25, 26 characters total)
    for (let i = 0; i < 26; ++i) {
        // Current character ko identify karo ASCII value se
        let currentChar = String.fromCharCode(i + 97);
        
        // Current character ka pehla (first) aur aakhri (last) occurrence dhoondo
        let l = s.indexOf(currentChar);
        let r = s.lastIndexOf(currentChar);
        
        // Agar pehla (l) aur aakhri (r) occurrence valid hain aur l < r hai, tab:
        if (l !== -1 && r !== -1 && l < r) {
            // Pehla aur aakhri occurrence ke beech ke unique characters count karo
            count += new Set(s.substring(l + 1, r)).size;
        }
    }

    // Final count return karo
    return count;
};

Yeh code ek function define karta hai jo given string mein 3 length wale palindromic subsequences ka count return karta hai. Chalo isse Hinglish mein step-by-step samajhte hain:

  1. Function Declaration & Initialization:

    • Function countPalindromicSubsequence ko define karte hain jo input mein ek string s lega aur ek number return karega.

    • Ek count variable ko initialize karenge zero se jo final answer store karega.

  2. Iterating over Characters:

    • ‘a’ se ‘z’ tak 26 lowercase English letters ko represent karte huye ek loop chalayenge (0 se 25 tak).

  3. Current Character Identification:

    • currentChar variable mein current character store karenge (String.fromCharCode(i + 97)) matlab ‘a’ + i (ASCII value).

  4. Finding First & Last Occurrence:

    • l aur r variables ko define karte hain jo currentChar ka pehla (indexOf) aur aakhri (lastIndexOf) occurrence batayenge.

  5. Check and Count:

    • Agar l aur r dono -1 nahi hain aur l < r, toh:

      • s.substring(l + 1, r) le kar beech ke characters ko consider karte hain.

      • Character ka set bana kar (jo unique characters ko represent karta hai), uska size count mein add karte hain.

  6. Returning Final Count:

    • Loop complete hone ke baad final count return karte hain jo unique palindromes ka total count batayega.

Solution

				
					

class Solution {
public:
    // Function that counts the number of palindromic subsequences
    int countPalindromicSubsequence(std::string s) {
        int count = 0; // Final count store karne ke liye variable initialize karo

        // 'a' se 'z' ke characters ke liye loop chalayenge (0 to 25, 26 characters total)
        for (int i = 0; i < 26; ++i) {
            // Current character ko identify karo ASCII value se
            char currentChar = static_cast<char>(i + 97);
            
            // Current character ka pehla (first) aur aakhri (last) occurrence dhoondo
            int l = s.find(currentChar);
            int r = s.rfind(currentChar);
            
            // Agar pehla (l) aur aakhri (r) occurrence valid hain aur l < r hai, tab:
            if (l != -1 && r != -1 && l < r) {
                // Pehla aur aakhri occurrence ke beech ke unique characters count karo
                count += std::unordered_set<char>(s.begin() + l + 1, s.begin() + r).size();
            }
        }

        // Final count return karo
        return count;
    }
};

    • Class Declaration: Ek Solution class banayi gayi hai jo function contain karti hai.

    • Function Definition:

      • Function Declaration: int countPalindromicSubsequence(std::string s) yeh function string s ko input leta hai aur integer return karta hai.

      • Count Initialization: Ek count variable initialize hota hai 0 se jo final result store karega.

    • Character Loop:

      • ‘a’ se ‘z’ tak ka loop: for (int i = 0; i < 26; ++i) se loop chalayenge 26 lowercase letters ke liye.

      • Identify Current Character: currentChar ek variable define hota hai jo current character ko store karta hai (i + 97 ASCII ka istemal karke).

    • Finding Occurrences:

      • Find First Occurrence: int l = s.find(currentChar) ye current character ka pehla occurrence find karta hai.

      • Find Last Occurrence: int r = s.rfind(currentChar) ye current character ka aakhri occurrence find karta hai.

    • Checking Validity:

      • Condition Check: Agar l aur r valid hain aur l < r hai:

        • Unique Characters Count (Between first and last occurrence): count += std::unordered_set<char>(s.begin() + l + 1, s.begin() + r).size(); Ye line pehla aur aakhri occurrence ke beech ke unique characters ka count add kar deti hai final count me.

    • Return Final Count:

      • Return Statement: Jab loop complete hota hai, final count return hota hai jo unique palindromic subsequences ka count represent karta hai.