Construct the Longest New String - Practice Coding Problems

Construct the Longest New String - Problem

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.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Balanced Case

$ Input: x = 1, y = 1, z = 1

› Output: 6

💡 Note: We have 1 "AA", 1 "BB", 1 "AB". Total A's = 2+1 = 3, Total B's = 2+1 = 3. Since they're equal, we can use all characters: length = 6. One valid arrangement: "AABBAB"

Example 2 — Imbalanced Case

$ Input: x = 2, y = 1, z = 1

› Output: 7

💡 Note: We have 2 "AA", 1 "BB", 1 "AB". Total A's = 4+1 = 5, Total B's = 2+1 = 3. Since |5-3| = 2 > 1, we use formula: 2×min(5,3)+1 = 7. One valid arrangement: "AABABAA"

Example 3 — No AB Strings

$ Input: x = 0, y = 1, z = 0

› Output: 2

💡 Note: We only have 1 "BB" string. Total A's = 0, Total B's = 2. We can use the entire "BB" string since it doesn't create "BBB". Length = 2.

Constraints

1 ≤ x, y, z ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Given counts of AA, BB, and AB strings

Analysis

Count total A's and B's, check balance

Construction

Build longest string without AAA/BBB

Key Takeaway

🎯 Key Insight: The maximum length depends on balancing A and B characters optimally - AB strings help bridge the gap between imbalanced counts

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is counting total A and B characters, then applying a mathematical formula based on character balance. If A's and B's are nearly balanced (difference ≤ 1), use all characters. Otherwise, use formula 2×min(A,B)+1. Best approach is Mathematical Formula with Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Balancing	O(1)	O(1)	Balance A and B characters optimally using mathematical insight
Brute Force Simulation	O(3^(x+y+z))	O(x+y+z)	Try all possible ways to arrange the strings and find maximum valid length
Mathematical Formula	O(1)	O(1)	Use precise mathematical analysis for optimal string construction

Greedy Balancing — Algorithm Steps

Count total A's: 2*x + z
Count total B's: 2*y + z
Use greedy strategy to balance A's and B's
Return maximum possible length without creating AAA or BBB

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Characters

Calculate total A's and B's from all strings

Check Balance

Determine if A's and B's are nearly balanced

Apply Formula

Use optimal formula based on balance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int abs_val(int a) {
    return a < 0 ? -a : a;
}

int solution(int x, int y, int z) {
    // Count total A's and B's
    int totalA = 2 * x + z;
    int totalB = 2 * y + z;
    
    // Balance the characters optimally
    if (abs_val(totalA - totalB) <= 1) {
        // Nearly balanced - can use all characters
        return totalA + totalB;
    } else {
        // Imbalanced - limited by the minority character
        return 2 * min(totalA, totalB) + 1;
    }
}

int main() {
    int x, y, z;
    scanf("%d", &x);
    scanf("%d", &y);
    scanf("%d", &z);
    printf("%d\n", solution(x, y, z));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Simple mathematical calculations

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Balancing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler