“The problem can be modeled as a

• The process evolves step by step
• Only a few conditions matter at any time
• You see:
• The problem says:

• “cooldown”
• “transaction”
• “valid / invalid”
• “transition”
• “sequence of actions”

30 MUST-DO INTERVIEW PROBLEMS

1. #
   Count Binary Substrings – LC 696
2. #
   Valid Parentheses String (Greedy bounds view) – LC 678
3. #
   Check If a Parentheses String Can Be Valid – LC 2116
4. #
   Number of Students Unable to Eat Lunch – LC 1700
5. #
   Maximum Score After Splitting String – LC 1422
6. #
   Decode String – LC 394
7. #
   Zigzag Conversion – LC 6
8. #
   Longest Turbulent Subarray – LC 978
9. #
   Find the Winner of a Circular Game – LC 1823
10. #
    Best Time to Buy and Sell Stock (1 Transaction, State View) – LC 121

• Valid/invalid transitions
• Running state updates
• Feasibility maintenance

1. #
   Best Time to Buy and Sell Stock with Cooldown – LC 309
2. #
   Best Time to Buy and Sell Stock with Fee – LC 714
3. #
   Best Time to Buy and Sell Stock III – LC 123
4. #
   Minimum Operations to Reduce X to Zero – LC 1658
5. #
   Minimum Swaps to Make Strings Equal – LC 1247
6. #
   Valid Parenthesis String (DP compression view) – LC 678
7. #
   Jump Game (State view) – LC 55
8. #
   Maximum Score From Removing Substrings – LC 1717
9. #
   Strange Printer – LC 664
10. #
    Number of Ways to Stay in the Same Place – LC 1269

• What are the states?
• What triggers a transition?
• Why is transition safe?

1. #
   Best Time to Buy and Sell Stock IV – LC 188
2. #
   Cherry Pickup II (state compression view) – LC 1463
3. #
   Minimum Number of Taps to Water a Garden – LC 1326
4. #
   Predict the Winner (state difference DP) – LC 486
5. #
   Maximum Alternating Subsequence Sum – LC 1911
6. #
   Maximum Sum of 3 Non-Overlapping Subarrays – LC 689
7. #
   Count Vowels Permutation – LC 1220
8. #
   Number of Ways to Paint N x 3 Grid – LC 1411
9. #
   Minimum Difficulty of a Job Schedule – LC 1335
10. #
    Domino and Tromino Tiling – LC 790

• Identifying minimal state set
• Avoiding full DP table
• Transition proof
• Sometimes greedy + state mix

“What are the

• Treating state problems as ad-hoc greedy
• Tracking too many variables instead of states
• Not explaining why a transition is forbidden
• Mixing DP and greedy without justification

1️⃣ Pattern in One Line

"Model the problem as a small set of states and define valid transitions between them."

2️⃣ Recognize It When...

• Process evolves step by step with constraints
• Trigger words: "cooldown", "at most K transactions", "cannot do X after Y", "valid sequence"
• Only a few conditions matter at any time
• Stock buying/selling, cooldowns, fees problems

3️⃣ Don't Confuse With...

• DP (P13) → state machine IS a form of DP but with explicitly named states
• Greedy (P9) → greedy makes one-time choices; state machine tracks ongoing validity
• Simulation → simulation just executes; state machine reasons about valid transitions

4️⃣ Approach in 3 Steps

1. #
   Identify all possible states (e.g., holding/not holding stock)
2. #
   Define transitions: what moves you from state A to state B?
3. #
   Track optimal value at each state, update at every step

5️⃣ Invariant to Maintain

"At every step, each state variable contains the optimal value achievable while being in that state after processing arr[0..i]."

6️⃣ Complexity to Justify

• Time: O(N × S) — N elements × S states
• Space: O(S) — only current state values needed
• Why: Fixed number of states processed once per element

7️⃣ Edge Cases to Always Check

• Single day/element — trivial state transition
• All prices decreasing — answer may be 0
• K = 0 transactions — return 0 immediately
• Cooldown = N — only one transaction possible
• State initialization — holding stock at day 0 = -prices[0]

8️⃣ One Line to Say in Interview

"I'll model this as a state machine — define states, write transitions, track optimal value per state — O(N) time and O(1) space."