Problem 1 Uber Security Team (Strong Password Checker) Solution

Topics Involved

• String Manipulation

Overview

1. We must satisfy length constraints, missing character types, and eliminate any consecutive repeating sequences of three or more characters.
2. If the password is too short, insertions can simultaneously fix the length deficit, missing character types, and repeating sequences.
3. If the password is too long, we strategically prioritize deletions on repeating sequences to minimize the remaining required replacements.

Approach

1. Counting Missing Types First, we scan the string to check if it contains at least one lowercase letter, one uppercase letter, and one digit. We count how many of these three categories are missing, storing it as missingTypes (which will be between 0 and 3).

2. Handling the Three Length Scenarios

• Length < 6: We need to add characters. A single insertion can break a repeating sequence, add a missing type, and fix the length simultaneously. The answer is simply max(6 - length, missingTypes).

• Length between 6 and 20: We only need replacements. A single replacement breaks a repeating sequence of 3. We calculate the total replacements needed for all repeating groups and return max(replacements, missingTypes).

• Length > 20: We must delete characters. To minimize replacements later, we delete characters from repeating sequences. We prioritize sequences where the length modulo 3 is 0, then 1, and finally 2, as this yields the most efficient reduction in required replacements.

Code Implementation

function strongPasswordChecker(s):
    n = length of s
    missingTypes = getMissingTypesCount(s) // Returns 0, 1, 2, or 3
    
    // Scenario 1: Password is too short
    if n < 6:
        return max(6 - n, missingTypes)
        
    repeats = [] // Store lengths of repeating sequences >= 3
    replacementsNeeded = 0
    
    // Find all repeating sequences
    i = 0
    while i < n:
        len = 1
        while i + len < n AND s[i] == s[i + len]:
            len = len + 1
        if len >= 3:
            repeats.push_back(len)
            replacementsNeeded = replacementsNeeded + (len / 3)
        i = i + len
        
    // Scenario 2: Password length is valid
    if n <= 20:
        return max(replacementsNeeded, missingTypes)
        
    // Scenario 3: Password is too long
    deleteCount = n - 20
    
    // Greedily reduce replacements by simulating deletions on repeats
    // Prioritize sequences where len % 3 == 0, then == 1, then == 2
    for mod from 0 to 2:
        for each seq in repeats:
            if seq % 3 == mod AND seq >= 3 AND deleteCount > 0:
                charsToRemove = min(deleteCount, mod + 1)
                seq = seq - charsToRemove
                deleteCount = deleteCount - charsToRemove
                // Recalculate replacements saved
                
    // Any remaining deletions are done arbitrarily
    return (n - 20) + max(remainingReplacements, missingTypes)

Time Complexity

• Time: O(N) - We iterate through the password string a constant number of times to count character types and repeating sequences.

• Space: O(N) - To store the lengths of the repeating sequences for processing deletions.

Problem2 

Kingdom of Eldoria (Royal Vault Heist) Solution

Topics-: 

• Dynamic Programming (1D Array)

• 0-1 Knapsack Optimization

Overview

1. Each chamber can only be robbed once within a strict total time limit, making this a variation of the classic 0-1 Knapsack optimization problem.
2. We first preprocess the input by multiplying both the base jewel value and the time required by the security level to get our true weights and values.
3. We then use a dynamic programming array to iteratively track the maximum possible jewel value achievable for every time increment up to the limit.

Approach

1. Preprocessing the Inputs

The raw inputs given for each chamber do not directly represent the final cost and reward. We must iterate through the given array and calculate the effectiveValue (Base Jewel Value $\times$ Security Level) and the actualTime (Time to Disable $\times$ Security Level) for every single chamber.

2. Dynamic Programming (0-1 Knapsack)

We create a DP array of size t + 1, where dp[j] represents the maximum jewel value we can steal exactly in j units of time. For each chamber, we loop backward through our DP array from the maximum time t down to the chamber's actualTime. At each step, we decide whether it is more profitable to skip the chamber or to rob it by checking max(dp[j], dp[j - actualTime] + effectiveValue).

Code Implementation

function maxJewelValue(n, t, m):
    // dp[j] will store the max value achievable in exactly 'j' time
    create array dp of size (t + 1) initialized to 0
    
    for i from 0 to n - 1:
        securityLevel = m[i][0]
        baseValue = m[i][1]
        baseTime = m[i][2]
        

        effectiveValue = baseValue * securityLevel
        actualTime = baseTime * securityLevel
        
        // Step 2: Update the DP array backwards to avoid re-using the same chamber
        for j from t down to actualTime:
            dp[j] = max(dp[j], dp[j - actualTime] + effectiveValue)
            
    // The maximum value found at the maximum time allowance
    return dp[t]

Time Complexity

• Time: O(N *T) - Where N is the number of chambers and T is the total time available. We loop through time T for every single chamber.

• Space: O(T) - We only need a single 1D array of size T + 1 to store the states, heavily optimizing our memory footprint compared to a 2D matrix.