Untitled

class Solution {
public:
    long long rob(vector<int>& nums, vector<int>& colors) {
        
        long long n = nums.size();
        vector<long long> dp(n);
        
        // Base case:
        // If there is only one house, we rob it.
        dp[0] = nums[0];
        
        for(long long i = 1; i < n; i++){
            
            long long aa = dp[i-1];   // Option 1: do not rob current house
            long long bb = 0;         // Option 2: rob current house (if valid)
            
            // If current and previous houses have same color
            if(colors[i] == colors[i-1]){
                
                // We cannot rob both i and i-1 together
                aa = dp[i-1];   // skip current
                
                // If we rob current, we must skip previous
                if(i > 1) bb = dp[i-2];
                bb += nums[i];
            }
            else{
                // If colors are different,
                // we can safely add current house to previous total
                aa = dp[i-1] + nums[i];
            }
            
            // Take maximum of robbing or skipping
            dp[i] = max(aa, bb);
        }
        
        return dp.back();
        
        /*
        Time Complexity (TC):
        We iterate once over the array of size n.
        Each step does constant work.
        So TC = O(n)

        Space Complexity (SC):
        We use a dp array of size n.
        So SC = O(n)
        */
    }
};