Practice Projects

Count Ways To Build Good Strings Javascript C++

Problem Statement

 

Aapko numbers zero, one, low aur high diye gaye hain. In numbers ke saath aap ek string bana sakte ho. Pehle aap ek khali string se shuru karte ho, aur har step pe aap yeh do cheezein kar sakte ho:

  • Character ‘0’ ko zero baar append kar sakte ho (matlab zero ke saath length barh jaati hai).
  • Character ‘1’ ko ek baar append kar sakte ho (one ke saath length barh jaati hai).

Yeh process kitni baar bhi perform kiya ja sakta hai.

Ek “good” string wo string hoti hai jo in process ke zariye banayi jaati hai aur uski length low aur high ke beech hoti hai (inclusive).

Aapko yeh decide karna hai ki kitni alag-alag “good” strings banayi ja sakti hain jo yeh properties satisfy karti hain. Kyunki answer bahut bada ho sakta hai, isliye aapko usse 109+710^9 + 7 se modulo karke return karna hai.

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1 

Output: 8 

Explanation: Ek possible valid “good” string hai “011”. Isse aise construct kiya ja sakta hai: “” -> “0” -> “01” -> “011”. \ Is example mein “000” se le kar “111” tak saari binary strings “good” strings hain.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2

Output: 5 

Explanation: “Good” strings hain “00”, “11”, “000”, “110”, aur “011”.

Constraints:

  • 1 <= low <= high <= 10510^5
  • 1 <= zero, one <= high
  1.  
Practice Projects

Count Ways To Build Good Strings Javascript C++

Ek "good" string banane ke liye, key yeh hai ki dynamic programming ka use karke har tarah ke different lengths ke valid strings ki ginti efficient tariqe se ki jaaye, saath hi saath constraints ka dhyan rakha jaaye.

Intuition

Dp array ko use karte hain jahan dp[i] track karta hai number of ways to create a string of length i. Khali string se shuru karke, hum iteratively longer strings build karte hain by appending zero ya one characters aur count ko modulo (10^9 + 7) ke saath rakhte hain.

Approach

Complexity

  • Time complexity: 
  • Space complexity: 

Solution

				
					class Solution {
    countGoodStrings(low, high, zero, one) {
        const mod = 1e9 + 7;
        const dp = Array(high + 1).fill(0);
        dp[0] = 1; // Base case: 1 way to create an empty string

        for (let i = 0; i <= high; i++) {
            if (dp[i] > 0) {
                if (i + zero <= high) {
                    dp[i + zero] = (dp[i + zero] + dp[i]) % mod;
                }
                if (i + one <= high) {
                    dp[i + one] = (dp[i + one] + dp[i]) % mod;
                }
            }
        }

        let result = 0;
        for (let i = low; i <= high; i++) {
            result = (result + dp[i]) % mod;
        }
        return result;
    }
}

Explanation

Class Declaration

class Solution {

  • Yeh ek class declare karta hai jiska naam Solution hai jo countGoodStrings method ko contain karta hai.

Method Signature

countGoodStrings(low, high, zero, one) {

  • Yeh method countGoodStrings define karti hai jo char parameters leti hai:

    • low: Strings ki length ka lower limit.

    • high: Strings ki length ka upper limit.

    • zero: Kitne 0s ko append kar sakte hain string ko extend karne ke liye.

    • one: Kitne 1s ko append kar sakte hain string ko extend karne ke liye.

Constants and Initial Setup

const mod = 1e9 + 7;
const dp = Array(high + 1).fill(0);
dp[0] = 1;

  • mod: Ek constant set karta hai 109+710^9 + 7 ko taaki integer overflow prevent ho sake aur result typical constraints ke andar rahen.

  • dp: Ek array initialize karta hai zeros ke saath, jiska size high + 1 hai dynamic programming ke liye. dp[i] represent karta hai number of ways to create a string of length i.

  • dp[0] = 1: Base case – ek tarika hai ek empty string create karne ka.

Dynamic Programming Loop

for (let i = 0; i <= high; i++) {
  if (dp[i] > 0) {
    if (i + zero <= high) {
      dp[i + zero] = (dp[i + zero] + dp[i]) % mod;
    }
    if (i + one <= high) {
      dp[i + one] = (dp[i + one] + dp[i]) % mod;
    }
  }
}

  • Loop lagata hai har value of i se 0 le kar high tak.

  • Check karta hai agar dp[i] greater than zero hai taaki ensure ho sake ki string create karne ke ways hain.

  • Agar zero ko append karna ya one ko append karna high se exceed nahi karta, toh dp[i + zero] aur dp[i + one] ko respectively update karta hai by adding dp[i] use karke. Modulo operation use karta hai taaki overflow prevent ho sake aur numbers manageable rahen.

Calculation of Result

let result = 0;
for (let i = low; i <= high; i++) {
  result = (result + dp[i]) % mod;
}
return result;

  • Ek variable result ko 0 par initialize karta hai.

  • Loop lagata hai low se high tak lengths ke liye.

  • Har valid length ke liye dp[i] ko result mein add karta hai, taking mod to handle large numbers.

  • Final count of “good” strings return karta hai jo specified range ke andar hain.

Solution

				
					class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        int mod = 1e9 + 7;
        vector<int> dp(high + 1, 0);
        dp[0] = 1; // Base case: 1 way to create an empty string.

        for (int i = 0; i <= high; i++) {
            if (dp[i] > 0) {
                if (i + zero <= high) {
                    dp[i + zero] = (dp[i + zero] + dp[i]) % mod;
                }
                if (i + one <= high) {
                    dp[i + one] = (dp[i + one] + dp[i]) % mod;
                }
            }
        }

        int result = 0;
        for (int i = low; i <= high; i++) {
            result = (result + dp[i]) % mod;
        }
        return result;
    }
};

Explanation

Class Declaration

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {

  • Yeh class Solution declare kar rahi hai jisme countGoodStrings method hai jo integer parameters low, high, zero, aur one ko accept karta hai.

Constants and Initial Setup

int mod = 1e9 + 7;
vector<int> dp(high + 1, 0);
dp[0] = 1; // Base case: 1 way to create an empty string.

  • mod: Ek constant set karta hai 109+710^9 + 7 ko taaki integer overflow prevent ho sake aur results manageable rahen.

  • dp: Ek vector initialize karta hai zeros ke saath, size high + 1 hai dynamic programming ke liye. dp[i] represent karta hai number of ways to create a string of length i.

  • dp[0] = 1: Base case – ek tarika hai ek empty string create karne ka.

Dynamic Programming Loop

for (int i = 0; i <= high; i++) {
    if (dp[i] > 0) {
        if (i + zero <= high) {
            dp[i + zero] = (dp[i + zero] + dp[i]) % mod;
        }
        if (i + one <= high) {
            dp[i + one] = (dp[i + one] + dp[i]) % mod;
        }
    }
}

  • Loop lagata hai i ke values from 0 to high tak.

  • Agar dp[i] greater than zero ho, toh ensure karta hai ki ways hain string of length i ko create karne ke liye.

  • Agar i + zero ya i + one high se exceed nahi karti, toh dp[i + zero] aur dp[i + one] ko respectively update karta hai by adding dp[i]. Modulo operation use karta hai taaki overflow ko rok sake aur numbers manageable rahen.

Calculation of Result

int result = 0;
for (int i = low; i <= high; i++) {
    result = (result + dp[i]) % mod;
}
return result;

  • Ek variable result ko 0 par initialize karta hai.

  • low se high tak lengths ke liye loop lagata hai.

  • Har valid length ke liye dp[i] ko result mein add karta hai, taking mod to handle large numbers.

  • Final count return karta hai “good” strings ka jo specified range ke andar hain.

channels4_banner