Practice/Amazon/Leetcode 276. Paint Fence

Leetcode 276. Paint Fence

CodingOptional

Problem

You are designing a decorative pattern for a linear arrangement of n positions. Each position must be assigned one of k available colors. However, there is a strict aesthetic constraint: no more than two consecutive positions can have the same color.

Calculate the total number of distinct valid color patterns that satisfy this constraint.

Requirements

1. Each position must be assigned exactly one color from the k available colors
2. At most two consecutive positions can share the same color (three or more in a row is invalid)
3. Return the total count of valid patterns
4. If there are no positions (n = 0), return 0

Constraints

• 0 ≤ n ≤ 50
• 1 ≤ k ≤ 105
• Time complexity should be O(n)
• Space complexity should be O(1) or O(n)

Examples

Example 1:

` Input: n = 3, k = 2 Output: 6 Explanation: Using colors A and B, the valid patterns are:

• AAB (A repeats twice, then B)
• ABA (alternating)
• ABB (A, then B repeats twice)
• BAA (B, then A repeats twice)
• BAB (alternating)
• BBA (B repeats twice, then A) All six patterns satisfy the constraint of at most two consecutive same colors. `

Example 2:

Input: n = 1, k = 1 Output: 1 Explanation: With one position and one color, there's exactly one way to color it.

Example 3:

` Input: n = 2, k = 3 Output: 9 Explanation: With 2 positions and 3 colors (A, B, C):

• Same color patterns: AA, BB, CC (3 ways)
• Different color patterns: AB, AC, BA, BC, CA, CB (6 ways) Total: 3 + 6 = 9 `