We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct the Longest New String

Number: 2850

Difficulty: Medium

Paid? No

Companies: Guidewire, Microsoft

Problem Description

You are given three integers x, y, and z. You have x strings equal to "AA", y strings equal to "BB", and z strings equal to "AB". You want to choose some (possibly all or none) of these strings and concatenate them in some order to form a new string. The new string must not contain "AAA" or "BBB" as a substring. Return the maximum possible length of such a new string.

Key Insights

  • We have pieces of fixed length (always 2 characters) that can be concatenated in any order.
  • The main constraint is to avoid any substring "AAA" or "BBB" which means we cannot allow three consecutive A’s or B’s.
  • When appending a piece, note that the characters at the junction may merge with the tail of the current string; therefore, we must carefully simulate the merging.
  • A dynamic programming (or DFS with memoization) solution can be designed where the state consists of the remaining counts (x, y, z) and the last up to two characters (i.e. a suffix) of the current string.
  • For each state, try to append any piece that does not violate the constraint by checking if the new suffix contains "AAA" or "BBB". Then update the state accordingly.
  • The total length increases by 2 for every piece appended, and our goal is to maximize the total appended length.

Space and Time Complexity

Time Complexity: O(x * y * z * C) where C is the number of possible suffix states (bounded by a small constant, at most 4 characters states)
Space Complexity: O(x * y * z * C) due to recursion stack and memoization storage.

Solution

We use a recursive depth-first search (DFS) with memoization. The state is defined by four parameters:

  1. The remaining counts of "AA", "BB", and "AB" pieces (x, y, z).
  2. The current suffix (last up to 2 characters) of the concatenated string.

For every state, we try appending one of the three available pieces (if available). Before appending, we concatenate the current suffix with the chosen piece and check if the resulting string (or its relevant suffix) contains "AAA" or "BBB". If appending does not violate the rule, we update the suffix to be the last two characters of the new string and continue recursively with decreased piece count.

The solution uses simple string operations to simulate the merging of pieces and verifies the constraints. We then choose the maximum length over all valid combinations.

Code Solutions

# Python solution for Construct the Longest New String

def constructLongestNewString(x, y, z):
    # memoization dictionary to cache computed results:
    # key: (x, y, z, suffix) and value: maximum cumulative length from that state.
    memo = {}

    def dfs(remAA, remBB, remAB, suffix):
        # If the state has been computed, return the memoized result.
        if (remAA, remBB, remAB, suffix) in memo:
            return memo[(remAA, remBB, remAB, suffix)]
        
        best_length = 0  # current best additional length from this state
        
        # Try appending "AA"
        if remAA > 0:
            candidate = suffix + "AA"  # simulate concatenation of current suffix and piece
            # Only need to check if candidate contains forbidden substring
            if "AAA" not in candidate and "BBB" not in candidate:
                # New suffix is the last 2 characters of the overall string
                new_suffix = candidate[-2:] if len(candidate) >= 2 else candidate
                # Recursively try next pieces after using one "AA"
                best_length = max(best_length, 2 + dfs(remAA - 1, remBB, remAB, new_suffix))
        
        # Try appending "BB"
        if remBB > 0:
            candidate = suffix + "BB"
            if "AAA" not in candidate and "BBB" not in candidate:
                new_suffix = candidate[-2:] if len(candidate) >= 2 else candidate
                best_length = max(best_length, 2 + dfs(remAA, remBB - 1, remAB, new_suffix))
        
        # Try appending "AB"
        if remAB > 0:
            candidate = suffix + "AB"
            if "AAA" not in candidate and "BBB" not in candidate:
                new_suffix = candidate[-2:] if len(candidate) >= 2 else candidate
                best_length = max(best_length, 2 + dfs(remAA, remBB, remAB - 1, new_suffix))
        
        memo[(remAA, remBB, remAB, suffix)] = best_length
        return best_length

    # Start with an empty suffix.
    return dfs(x, y, z, "")

# Example test cases
print(constructLongestNewString(2, 5, 1))  # Expected output: 12
print(constructLongestNewString(3, 2, 2))  # Expected output: 14
← Back to All Questions