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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct the Longest New String

Difficulty: Medium

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. This new string must not contain "AAA" or "BBB" as a substring. Return the maximum possible length of the new string.

Key Insights

  • The strings "AA" and "BB" can only be used in a way that prevents the creation of the substrings "AAA" or "BBB".
  • The string "AB" can be used to separate "AA" and "BB", allowing for more flexible combinations.
  • The optimal way to form the longest string is to alternate between "AA" and "BB", using "AB" as needed to maintain the constraints.

Space and Time Complexity

Time Complexity: O(1) - The solution involves simple arithmetic calculations and comparisons, independent of input size. Space Complexity: O(1) - Only a fixed number of variables are used, regardless of the input values.

Solution

To solve this problem, we can employ a greedy approach:

  1. Count the Total Length: Each "AA" contributes 2, each "BB" contributes 2, and each "AB" contributes 2 to the total length.
  2. Determine the Limiting Factor: The maximum number of "AA" and "BB" pairs that can be added is limited by the smaller count between x and y. If one type runs out, we can use "AB" to blend the remaining type.
  3. Calculate the Result: The maximum length can be computed based on how many pairs we can create without violating the constraints.

This approach uses basic arithmetic operations and comparisons to find the optimal arrangement of strings.

Code Solutions

def constructLongestString(x, y, z):
    # Calculate the maximum length considering pairs of "AA" and "BB"
    total_length = 0

    # Use the minimum of x and y to form pairs
    pairs = min(x, y)
    total_length += pairs * 4  # Each pair contributes 4
    
    x -= pairs
    y -= pairs

    # Add remaining "AB" strings
    total_length += z * 2  # Each "AB" contributes 2

    # Now we can use remaining "AA" or "BB"
    remaining = x + y
    if remaining > 0:
        # If we have remaining "AA" or "BB", we can only add in pairs
        total_length += (remaining // 2) * 2

        # If there's one remaining string, we can add 2 more for that
        if remaining % 2 == 1:
            total_length += 2

    return total_length
← Back to All Questions