The Number of Ways to Select Buildings problem gives you a binary string representing buildings (0 or 1). Count the number of ways to select 3 buildings at indices i < j < k where no two adjacent selected buildings are of the same type — i.e., the sequence forms "010" or "101". This coding problem uses DP with prefix counts.
DE Shaw, Amazon, and Dream11 ask this to test efficient triplet counting with the "fix the middle element" technique using prefix sums. The string, dynamic programming, and prefix sum interview pattern is directly demonstrated.
Fix middle element with prefix counts. For each middle position j with value v: count how many valid (i,k) pairs exist. For "010" pattern: j has value 0, count i<j with value 1, count k>j with value 1. For "101": j has value 1, count 0s on each side. Maintain prefix count of 0s and 1s seen so far. For suffix counts, precompute or maintain running counts from the right.
Two-pass approach: for each j, ways += (count of 1s before j) * (count of 1s after j) if s[j]='0', plus (count of 0s before j) * (count of 0s after j) if s[j]='1'.
s="001101". Pattern "010" or "101". Pre-compute suffix 0s and 1s. For each j:
Triplet pattern counting (fix middle, multiply left/right counts) is a standard O(n) technique. Precompute prefix counts of 0s and 1s, and their suffix counterparts. For each middle position, the product of left-matching count and right-matching count gives the number of valid triplets with that middle. Practice "count subsequences of pattern XYX" using this fix-middle approach across various pattern types.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Find the Original Typed String II | Hard | Solve | |
| Minimum White Tiles After Covering With Carpets | Hard | Solve | |
| Number of Beautiful Partitions | Hard | Solve | |
| Maximum Number of Subsequences After One Inserting | Medium | Solve | |
| Jump Game VII | Medium | Solve |
