Practice Projects

Count Vowel Strings in Ranges

Problem Statement

Aapko ek 0-indexed array of strings “words” aur ek 2D array of integers “queries” diye gaye hain.

Har query queries[i] = [li, ri] aapse puch rahi hai ke words ke range li se ri (dono inclusive) mein kitne strings hain jo vowel se start aur end hote hain.

Aapko ek array “ans” return karna hai jiska size ke barabar hoga, aur ans[i] mein ith query ka answer hoga.

Note: Vowel letters hain ‘a’, ‘e’, ‘i’, ‘o’, aur ‘u’.

Example 1:

Input: words = [“aba”,”bcb”,”ece”,”aa”,”e”], queries = [[0,2],[1,4],[1,1]] Output: [2,3,0]

Explanation:

  • Jo strings vowel se start aur end hoti hain wo hain “aba”, “ece”, “aa”, aur “e”.

  • [0,2] query ke liye answer hoga 2 (strings “aba” aur “ece”).

  • [1,4] query ke liye answer hoga 3 (strings “ece”, “aa”, “e”).

  • [1,1] query ke liye answer hoga 0.

Example 2: Input: words = [“a”,”e”,”i”], queries = [[0,2],[0,1],[2,2]] Output: [3,2,1]

Explanation:

  • Har string is condition ko satisfy karti hai, isiliye hum return karte hain [3,2,1].

Constraints:

  • 1 <= <= 105

  • 1 <= words[i].length <= 40

  • words[i] sirf lowercase English letters se bane hote hain.

  • sum(words[i].length) <= 3 * 105

  • 1 <= <= 105

  • 0 <= li <= ri <

Practice Projects

Count Vowel Strings in Ranges

Vowel Strings Identify Karna: Sabse pehla step hai yeh dekhna ki kaunse strings vowel se start aur vowel pe end hote hain. Bas thoda focus zaroori hai.
Range Pr Queries Apply Karna: Queries aapko ek range deti hain (li to ri), aur aapko bas yeh count karna hai ki kitne strings us range mein hain, jo vowel se start aur end hote hain.
- Vowel Set Banana: Sab vowels ko ek set mein rakh lo - yeh help karega quick check karne mein ki koi character vowel hai ya nahi.
- Helper Function: Ek helper function likhna, jo check karega ki koi word vowel se start aur end hota hai ya nahi.
- Loop Thru Queries: Ab, har query ke liye iterate karke unhe range mein check karo.
- Count Ke Saath Update Karna: Har query ka count store karna hain jo ki find karega kitne vowel strings hain us range mein.

Intuition

pehle aap vowels ko set mein store karte ho, phir har query ke liye range check karte ho ki kaunse strings vowel se start aur end hote hain, aur count ko result array mein store karte ho. Finally, result array ko return karte ho. Yeh approach simple, efficient, aur samajhne mein aasan hai.

Approach
Time Complexity:

  1. Har Query Check Karna: Hum har query ko queries array ke through iterate karte hain. Agar q queries hain, toh is part ki time complexity O(q) hogi.

  2. Range Mein Har Word Check Karna: Har query ke liye, hum [li, ri] range mein har word ko check karte hain. Jo zyada se zyada words hum check karna padega woh words array ki length hain, jo n hai. Worst case mein, hum sab n words ko har query ke liye check kar sakte hain, jo time complexity O(n) per query banaata hai.

  3. Word Ko Vowel String Check Karna: Yeh check karna ki koi word vowel se start aur end hota hai, involves checking the first and last character, joh constant time O(1) mein hota hai.

Inhe combine karke, worst case scenario mein time complexity O(q * n) hogi, jahan q number of queries hain aur n number of words hain.

Space Complexity:

  1. Results Array Ka Space: Hum har query ke results ko ek array results mein store karte hain, jiska length queries ke barabar hai, toh yeh part O(q) space use karta hai.

  2. Vowels Set Ka Space: Vowels set ek constant-sized set hai jo 5 characters contain karta hai, toh yeh part O(1) space use karta hai.

  3. Auxiliary Space Computations: Results aur vowels set ke alawa, algorithm ko significant additional space ki zaroorat nahi.

Isliye, overall space complexity O(q) hai.

Solution

				
					function vowelStrings(words, queries) {
    // Vowels ka ek set create karo
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const results = [];

    // Helper function jo check karega agar string vowel se start aur end hoti hai
    function isVowelString(word) {
        return vowels.has(word[0]) && vowels.has(word[word.length - 1]);
    }

    // Har query ke liye loop karo
    for (const [li, ri] of queries) {
        let count = 0;

        // Range [li, ri] mein har word ko check karo
        for (let i = li; i <= ri; i++) {
            if (isVowelString(words[i])) count++;
        }

        results.push(count);
    }

    return results;
}

// Example 1
const words1 = ["aba", "bcb", "ece", "aa", "e"];
const queries1 = [[0, 2], [1, 4], [1, 1]];

console.log(vowelStrings(words1, queries1)); // Output: [2, 3, 0]

Steps:

  1. Vowels Set Create Karna:

    javascript
     const vowels = new Set(['a', 'e', 'i', 'o', 'u']);

    Pehle, hum ek set banate hain jo sab vowels (a, e, i, o, u) ko contain karta hai. Is set se hum vowels ko quickly identify kar sakte hain.

  2. Results Array Initialize Karna:

    javascript
     const results = [];

    Yeh array har query ke answers store karega.

  3. Helper Function:

    javascript
     function isVowelString(word) { 
     return vowels.has(word[0]) && vowels.has(word[word.length - 1]); 
 }
`` 
Helper function `isVowelString` banate hain jo check karta hai ki string vowel se start aur end hoti hai ya nahi.

  4. Loop Through Queries:

    javascript
     for (const [li, ri] of queries) {

    Har query ko loop karte hain. Har query ek range [li, ri] contain karti hai.

  5. Initialize Count:

    javascript
     let count = 0;

    Har query ke liye count variable initialize karte hain jo string count karega jo vowel se start aur end hoti hai.

  6. Check Words in Range:

    javascript
     for (let i = li; i <= ri; i++) { 
     if (isVowelString(words[i])) count++; 
 }

    Range [li, ri] ke har word ko check karte hain ki kya wo vowel string hai. Agar haan, toh count increment karte hain.

  7. Store Results:

    javascript
     results.push(count);

    Har query ka count results array mein store karte hain.

  8. Return Results:

    javascript
     return results;

    Akhri mein, results array ko return karte hain jo har query ka answer deta hai.

Solution

				
					class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size(); // Words ki length n store karo
        vector<int> v(n+1, 0); // Ek vector v banao jisme initial value 0 ho

        // Har word ko check karo agar wo vowel se start aur end hota hai
        for (int i = 0; i < n; i++) {
            if ((words[i][0] == 'a' || words[i][0] == 'e' || words[i][0] == 'i' || words[i][0] == 'o' || words[i][0] == 'u') &&
                (words[i][words[i].length() - 1] == 'a' || words[i][words[i].length() - 1] == 'e' || words[i][words[i].length() - 1] == 'i' || words[i][words[i].length() - 1] == 'o' || words[i][words[i].length() - 1] == 'u')) {
                v[i + 1] = 1; // Agar word vowel se start aur end hota hai, to v[i+1] ko 1 se mark karo
            }
            v[i + 1] += v[i]; // Prefix sum calculate karo
        }

        vector<int> ans; // Result vector
        for (auto& i : queries) {
            ans.push_back(v[i[1] + 1] - v[i[0]]); // Query ke liye answer calculate karke ans mein push karo
        }

        return ans; // Result ans return karo
    }
};

  • Words Ki Length Aur Prefix Sum Array:

    cpp
    int n = words.size();
vector<int> v(n+1, 0);

    n ko words ki length mein store karte hain aur ek vector v create karte hain jisme initially sab 0 hota hai. Isse hum prefix sum array banayenge.

  • Har Word Ko Check Karna:

    cpp
    for (int i = 0; i < n; i++) {
    if ((words[i][0] == 'a' || words[i][0] == 'e' || words[i][0] == 'i' || words[i][0] == 'o' || words[i][0] == 'u') &&
        (words[i][words[i].length() - 1] == 'a' || words[i][words[i].length() - 1] == 'e' || words[i][words[i].length() - 1] == 'i' || words[i][words[i].length() - 1] == 'o' || words[i][words[i].length() - 1] == 'u')) {
        v[i + 1] = 1;
    }
    v[i + 1] += v[i];
}

    Is loop mein, har word ko check karte hain ki kya wo vowel se start aur end hota hai:

    • Pehli condition: words[i][0] (first character) vowel hona chahiye.

    • Dusri condition: words[i][words[i].length() - 1] (last character) vowel hona chahiye.

    Agar dono conditions satisfy hoti hain, toh v[i + 1] ko 1 set karte hain. Fir, prefix sum calculate karte hain aur v[i + 1] mein previous prefix sum ko add karte hain.

  • Queries Ka Solution:

    cpp
    vector<int> ans;
for (auto& i : queries) {
    ans.push_back(v[i[1] + 1] - v[i[0]]);
}

    Ab, har query ke liye, prefix sum array ka use karke answer calculate karte hain:

    • v[i[1] + 1] mein prefix sum store hota hai from start to ri.

    • v[i[0]] mein prefix sum store hota hai from start to li-1.

    • Difference v[i[1] + 1] - v[i[0]] dega count of vowel strings within range [li, ri].

  • Result Return Karna:

    cpp
    return ans;

    Finally, sab queries ke answers ans vector mein store hote hain jise hum return karte hain.

channels4_banner