2222. Number of Ways to Select Buildings

MediumStringDynamic ProgrammingPrefix Sum
Leetcode Link

Problem Description

In LeetCode's problem, you are provided with a binary string s representing a street of buildings. A '0' represents an office, and a '1' represents a restaurant. The task is to count the number of valid ways to select a sequence of three buildings for inspection. However, a valid sequence cannot include two consecutive buildings of the same type. This means you cannot have "000" or "111" as part of your selected sequence. For example, if s = "0101", there are two valid sequences: "010" and "101". The goal is to calculate the total number of such valid sequences across the entire string.

Intuition

The intuition behind the solution is to leverage the constraints provided. Since we cannot select two buildings of the same type consecutively, a valid sequence can only be "010" or "101". We need to count the occurrences of these patterns.

We know the total counts of '0's and '1's in the string upfront as cnt0 and cnt1. For each character in the string, if it's a '0', then it can be the middle building in a "101" pattern. The number of valid patterns with this '0' in the middle is the count of '1's encountered so far times the count of '1's that are yet to be seen (cnt1 - c1). Similarly, if the character is a '1', it can be the middle building in a "010" pattern, and the number of valid patterns is the count of '0's seen so far times the count of '0's yet to be seen (cnt0 - c0).

By iterating over the string and updating the counts of '0's and '1's seen so far (c0 and c1), we can accumulate the number of valid sequences into ans.

Learn more about Dynamic Programming and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Solution Approach

The solution makes use of a single-pass algorithm to count the number of valid sequences. Here is a step-by-step breakdown of the algorithm using the code provided:

  1. Calculate the total number of '0's (cnt0) in the string: cnt0 = s.count("0").
  2. Calculate the total number of '1's (cnt1) by subtracting cnt0 from the length of the string, n.
  3. Initialize two counters c0 and c1 to keep track of the number of '0's and '1's encountered so far as we iterate through the string.
  4. Initialize a variable ans to accumulate the answer, which is the total count of valid ways.
  5. Iterate over each character c in the string s:
    • If c is '0', it can potentially be the middle of a "101" sequence. The number of such sequences involving this particular '0' is c1 (the number of '1's already seen) multiplied by (cnt1 - c1) (the number of '1's after this '0'). Add this to ans.
    • Increment c0 to indicate that we've seen an additional '0'.
    • If c is '1', the same logic applies, only now it could be the center of a "010" sequence. Calculate the valid sequences by multiplying c0 by (cnt0 - c0) and add it to ans.
    • Increment c1 accordingly.
  6. Once the iteration is complete, ans will contain the total number of valid sequences, which we return.

This approach is efficient because it requires only a single pass through the string, and thus has a time complexity of O(n), where n is the length of the string. There is no need for nested loops, which would increase the complexity. The space complexity is O(1) since only a constant amount of extra space is used—no additional data structures are needed. The insight that each '0' or '1' can potentially be the center of a valid sequence, and the precalculated total counts of each type of building, allow us to compute the answer with this direct method.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's walk through an example to illustrate the solution approach, using the binary string s = "0101010".

First, we count the number of '0's (cnt0) and '1's (cnt1) in the string:

  • cnt0 = s.count("0") = 4
  • cnt1 = len(s) - cnt0 = 7 - 4 = 3

Now, we initialize two counters c0 and c1 to keep track of the number of '0's and '1's encountered as we iterate:

  • c0 = 0
  • c1 = 0

We also initialize ans to accumulate the total count of valid ways:

  • ans = 0

Now, we start iterating over the string s.

  • Iteration 1: We encounter a '0'. It cannot form a "101" sequence as no '1's have been seen so far (c1 = 0). We increment c0.

    • c0 = 1
    • c1 = 0
    • ans remains 0

  • Iteration 2: We encounter a '1'. It can be the middle of a "010" sequence. There is 1 '0' before it and 3 '0's after it.

    • Valid "010" sequences with this '1': c0 * (cnt0 - c0) = 1 * (4 - 1) = 3
    • c0 = 1
    • c1 = 1
    • ans = ans + 3 = 3

  • Iteration 3: We encounter a '0'. We've seen 1 '1' so far and have 2 '1's remaining.

    • Valid "101" sequences with this '0': c1 * (cnt1 - c1) = 1 * (3 - 1) = 2
    • c0 = 2
    • c1 = 1
    • ans = ans + 2 = 5

  • Iteration 4: We encounter a '1'. There are 2 '0's before and 2 '0's after.

    • Valid "010" sequences with this '1': c0 * (cnt0 - c0) = 2 * (4 - 2) = 4
    • c0 = 2
    • c1 = 2
    • ans = ans + 4 = 9

  • Iteration 5: We encounter a '0'. Now we have 2 '1's before and 1 '1' after.

    • Valid "101" sequences with this '0': c1 * (cnt1 - c1) = 2 * (3 - 2) = 2
    • c0 = 3
    • c1 = 2
    • ans = ans + 2 = 11

  • Iteration 6: We encounter a '1'. There are 3 '0's before and 1 '0' after.

    • Valid "010" sequences with this '1': c0 * (cnt0 - c0) = 3 * (4 - 3) = 3
    • c0 = 3
    • c1 = 3
    • ans = ans + 3 = 14

  • Iteration 7: We encounter the final '0'. There are 3 '1's before but no '1's are after, so it cannot form a "101" sequence.

    • c0 = 4
    • c1 = 3
    • ans remains 14

After completing the iteration, ans = 14. So there are 14 valid ways to select sequences of buildings for inspection from the given string "0101010".

Solution Implementation

1class Solution:
2    def numberOfWays(self, s: str) -> int:
3        # Calculate the length of the string.
4        length_of_string = len(s)
5      
6        # Count the number of '0's in the string.
7        count_of_zeros = s.count("0")
8      
9        # Calculate the number of '1's in the string by subtracting the number of '0's from the total length.
10        count_of_ones = length_of_string - count_of_zeros
11      
12        # Initialize counters for the number of '0's and '1's that have been encountered so far.
13        running_count_zeros = 0
14        running_count_ones = 0
15      
16        # Initialize the answer to track the number of ways.
17        number_of_ways = 0
18      
19        # Iterate over the characters in the string.
20        for char in s:
21            if char == "0":
22                # If the current character is '0', calculate the contribution to the number of ways by considering
23                # the number of '1's encountered so far and the number of '1's yet to be encountered.
24                number_of_ways += running_count_ones * (count_of_ones - running_count_ones)
25              
26                # Increment the counter for '0's encountered.
27                running_count_zeros += 1
28            else:
29                # If the current character is '1', calculate the contribution to the number of ways by considering
30                # the number of '0's encountered so far and the number of '0's yet to be encountered.
31                number_of_ways += running_count_zeros * (count_of_zeros - running_count_zeros)
32              
33                # Increment the counter for '1's encountered.
34                running_count_ones += 1
35      
36        # Return the total number of ways.
37        return number_of_ways
38
1class Solution {
2    // Method to count the number of ways to form a "010" or "101" pattern in the given string.
3    public long numberOfWays(String s) {
4        // Length of the input string.
5        int length = s.length();
6        // Counter for zeros in the input string.
7        int countZeros = 0;
8      
9        // Count the number of zeros in the input string.
10        for (char c : s.toCharArray()) {
11            if (c == '0') {
12                countZeros++;
13            }
14        }
15      
16        // Counter for ones, which is the total length minus the number of zeros.
17        int countOnes = length - countZeros;
18        // Variable to store the total number of patterns found.
19        long totalWays = 0;
20        // Temp counters for zeros and ones as we iterate through the string.
21        int tempCountZeros = 0, tempCountOnes = 0;
22      
23        // Iterate through the characters of the string to count the patterns.
24        for (char c : s.toCharArray()) {
25            if (c == '0') {
26                // When we find a '0', we increase the total count of valid patterns found
27                // by the number of '1's found before multiplied by the number of '1's that
28                // can potentially come after this '0' to complete the pattern.
29                totalWays += tempCountOnes * (countOnes - tempCountOnes);
30                // Increase the temporary count of zeros since we encountered a '0'.
31                tempCountZeros++;
32            } else {
33                // Similarly, when we find a '1', we increase the count of valid patterns by
34                // the temporary count of '0's multiplied by the number of '0's that can come
35                // after to complete the pattern.
36                totalWays += tempCountZeros * (countZeros - tempCountZeros);
37                // Increase the temporary count of ones since we encountered a '1'.
38                tempCountOnes++;
39            }
40        }
41      
42        // Return the total number of patterns found.
43        return totalWays;
44    }
45}
46
1class Solution {
2public:
3    long long numberOfWays(string s) {
4        // Get the length of the string
5        int stringLength = s.size();
6      
7        // Initialize count of zeros in the string
8        int countOfZeros = 0;
9      
10        // Loop through the string to count the number of zeros
11        for (char character : s) {
12            countOfZeros += character == '0';
13        }
14      
15        // Calculate the count of ones as the remaining characters
16        int countOfOnes = stringLength - countOfZeros;
17      
18        // Initialize counters for zeros and ones processed so far
19        int zerosProcessed = 0, onesProcessed = 0;
20      
21        // Initialize the answer which will store the total number of ways
22        long long totalWays = 0;
23      
24        // Loop through the string to calculate the total count of valid sequences
25        for (char character : s) {
26            if (character == '0') {
27                // For each zero, pair it with previously encountered ones
28                // and potential ones that could come later in the string
29                totalWays += onesProcessed * (countOfOnes - onesProcessed);
30                // Increment the count of processed zeros
31                ++zerosProcessed;
32            } else {
33                // For each one, pair it with previously encountered zeros
34                // and potential zeros that could come later in the string
35                totalWays += zerosProcessed * (countOfZeros - zerosProcessed);
36                // Increment the count of processed ones
37                ++onesProcessed;
38            }
39        }
40      
41        // Return the total number of valid ways to order substrings "010" and "101"
42        return totalWays;
43    }
44};
45
1// TypeScript function to count number of ways to split a string into "010" and "101" substrings
2function numberOfWays(s: string): number {
3    // Get the length of the string
4    let stringLength: number = s.length;
5  
6    // Initialize count of zeros in the string
7    let countOfZeros: number = 0;
8  
9    // Loop through the string to count the number of zeros
10    for (let character of s) {
11        countOfZeros += character === '0' ? 1 : 0;
12    }
13  
14    // Calculate the count of ones as the remaining characters
15    let countOfOnes: number = stringLength - countOfZeros;
16  
17    // Initialize counters for zeros and ones processed so far
18    let zerosProcessed: number = 0;
19    let onesProcessed: number = 0;
20  
21    // Initialize the total number of ways to pair "010" and "101"
22    let totalWays: number = 0;
23  
24    // Loop through the string to calculate the total count of valid sequences
25    for (let character of s) {
26        if (character === '0') {
27            // For each zero, pair it with previously encountered ones
28            // and potential ones that could come later in the string
29            totalWays += onesProcessed * (countOfOnes - onesProcessed);
30            // Increment the count of processed zeros
31            zerosProcessed++;
32        } else {
33            // For each one, pair it with previously encountered zeros
34            // and potential zeros that could come later in the string
35            totalWays += zerosProcessed * (countOfZeros - zerosProcessed);
36            // Increment the count of processed ones
37            onesProcessed++;
38        }
39    }
40  
41    // Return the total number of valid ways to order substrings "010" and "101"
42    return totalWays;
43}
44
45// Example Usage
46// const ways: number = numberOfWays("001101");
47
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

The given Python code aims to count the number of ways to select three characters from the string s, such that the selected characters form the pattern "010" or "101".

Time Complexity

The time complexity of the code is O(n), where n is the length of the string s.

  • Calculating cnt0 using s.count("0") requires a single pass over the string, which is O(n).
  • The subsequent loop iterates over each character in the string once, which is O(n).
  • Inside the loop, the operations are constant time, such as updating counters and calculating the values for ans.

Therefore, the overall time complexity is the sum of the two O(n) operations, which is still O(n) since constant factors are ignored.

Space Complexity

The space complexity of the code is O(1).

  • The variables cnt0, cnt1, c0, c1, and ans are all integer counters that use a fixed amount of space.
  • No additional data structures that grow with the input size are used.

Thus, the space required does not scale with the size of the input s, resulting in a constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫