Reorganize String (No Two Adjacent Same)

📋

Problem

Imagine you are organizing a playlist where no two songs by the same artist should play consecutively to keep the audience engaged.

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. If such an arrangement is not possible, return an empty string. Otherwise, return any valid rearrangement.

1 ≤ s.length ≤ 10^5s consists of lowercase English letters only

Edge cases: Single character string → always valid, output same characterAll characters are the same → no valid rearrangement, output empty stringString with two characters both same → no valid rearrangement, output empty string

</>

IDE

def reorganizeString(s: str) -> str:public String reorganizeString(String s)string reorganizeString(string s)function reorganizeString(s)

def reorganizeString(s: str) -> str:
    # Write your solution here
    pass

class Solution {
    public String reorganizeString(String s) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string reorganizeString(string s) {
    // Write your solution here
    return "";
}

function reorganizeString(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: aabReturning original string without rearrangement even when adjacent duplicates exist.✅ Implement frequency counting and use a max heap to rearrange characters to avoid adjacency.

Wrong: aaReturning input string when no valid rearrangement exists (e.g., all characters same).✅ Add a check for max frequency > (n+1)/2 and return empty string if true.

Wrong: aaaabcGreedy approach that does not hold back previously used character causing adjacent duplicates.✅ Use a variable to store last used character and reinsert it into heap only after placing a different character.

Wrong: abcabcabIncorrect handling of equal frequency characters leading to adjacent duplicates.✅ Always pick two different characters from heap each iteration and reinsert if counts remain.

Wrong: TLE or timeoutUsing brute force or backtracking approach with factorial complexity.✅ Implement a heap-based greedy solution with O(n log k) complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Think about common greedy pitfalls and how to avoid placing the same character twice in a row.

Optimize your solution to run efficiently on large inputs using appropriate data structures.

t1_01basic

Input{"s":"aab"}

Expected"aba"

⏱ Performance - must finish in 2000ms

One possible rearrangement is 'aba' where no two adjacent characters are the same.

💡 Think about placing the most frequent characters first to avoid adjacency.

💡 Use a max heap to always pick the character with the highest remaining count.

💡 Pop two most frequent characters alternately and append them to the result.

Why it failed: Returned string has adjacent identical characters or incorrect length. Fix by ensuring characters are placed alternately using a max heap and checking counts before placement.

✓ Correct rearrangement with no two adjacent characters the same.

t1_02basic

Input{"s":"aaabc"}

Expected"abaca"

⏱ Performance - must finish in 2000ms

One valid rearrangement is 'abaca' where no two adjacent characters are the same.

💡 Count frequencies and verify if any character count exceeds half the string length.

💡 Use a priority queue to pick characters with highest frequency first.

💡 Alternate characters by popping top two from the heap and re-inserting if still available.

Why it failed: Output has adjacent duplicates or missing characters. Fix by checking frequency constraints and using a max heap to interleave characters properly.

✓ Valid rearrangement with no adjacent duplicates.

t2_01edge

Input{"s":""}

Expected""

⏱ Performance - must finish in 2000ms

Empty string input should return empty string as no rearrangement needed.

💡 Consider the base case of empty input.

💡 Return empty string immediately if input length is zero.

💡 No rearrangement needed for empty input.

Why it failed: Code crashes or returns non-empty for empty input. Fix by adding a base case to return empty string when input is empty.

✓ Correctly handles empty input by returning empty string.

t2_02edge

Input{"s":"a"}

Expected"a"

⏱ Performance - must finish in 2000ms

Single character string is always valid and should return the same character.

💡 Check if input length is 1 and return it directly.

💡 No rearrangement needed for single character.

💡 Ensure code does not alter single character input.

Why it failed: Code returns empty or altered string for single character input. Fix by returning input directly if length is 1.

✓ Correctly returns single character string unchanged.

t2_03edge

Input{"s":"aa"}

Expected""

⏱ Performance - must finish in 2000ms

Two identical characters cannot be rearranged to avoid adjacency, so return empty string.

💡 Check if any character frequency exceeds half the string length rounded up.

💡 If yes, return empty string immediately.

💡 This prevents impossible rearrangements.

Why it failed: Code returns non-empty string with adjacent duplicates. Fix by adding frequency check and returning empty string if max frequency > (n+1)/2.

✓ Correctly returns empty string for impossible rearrangement.

t3_01corner

Input{"s":"aaabbc"}

Expected"ababac"

⏱ Performance - must finish in 2000ms

Valid rearrangement interleaves the most frequent characters to avoid adjacency.

💡 Beware of greedy approaches that pick characters without considering future placement.

💡 Use a max heap and store previously used character temporarily to avoid immediate reuse.

💡 Reinsert characters back into heap only after placing a different character.

Why it failed: Greedy approach picks highest frequency character repeatedly causing adjacent duplicates. Fix by holding last used character out of heap until next iteration.

✓ Correctly avoids adjacent duplicates by managing heap and previous character.

t3_02corner

Input{"s":"aaabbbccc"}

Expected"abacacbcb"

⏱ Performance - must finish in 2000ms

Even distribution of characters with equal frequency requires careful interleaving.

💡 Check if your solution handles multiple characters with same max frequency.

💡 Use a max heap to always pick two different characters alternately.

💡 Ensure no character is placed twice consecutively by tracking last used character.

Why it failed: Output has adjacent duplicates due to not handling equal frequency characters properly. Fix by always picking two different characters from heap each iteration.

✓ Correctly interleaves characters with equal frequency.

t3_03corner

Input{"s":"aaaaabc"}

Expected""

⏱ Performance - must finish in 2000ms

One character frequency exceeds half the string length, no valid rearrangement possible.

💡 Check max frequency against (n+1)/2 to detect impossible cases.

💡 Return empty string immediately if condition fails.

💡 Avoid attempting rearrangement when impossible.

Why it failed: Code attempts rearrangement and returns invalid string with adjacent duplicates. Fix by adding max frequency check and returning empty string if condition violated.

✓ Correctly returns empty string for impossible rearrangement.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n log k) heap-based solution to complete within 2 seconds.

💡 Brute force or backtracking will time out due to factorial complexity.

💡 Use a max heap to achieve O(n log k) time complexity.

💡 Avoid unnecessary string concatenations inside loops.

Why it failed: Solution times out due to exponential or quadratic complexity. Fix by implementing a heap-based greedy approach with O(n log k) complexity.

✓ Solution runs efficiently within time limits using heap-based greedy approach.

Practice

1. You are given an array where each element represents the maximum jump length from that position. You need to determine if you can reach the last index starting from the first index. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Dynamic Programming with bottom-up tabulation to check reachability for each index

B. Breadth-first search using a queue to explore reachable indices level by level

C. Depth-first search exploring all possible jump paths recursively without memoization

D. Greedy algorithm tracking the maximum reachable index while iterating through the array

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if the last index is reachable from the first index using jumps defined by array values.

2. Step 2: Identify optimal approach

   Greedy approach efficiently tracks the furthest reachable index in one pass, guaranteeing O(n) time complexity, unlike exhaustive search or DP which are slower.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy approach is linear and optimal for this problem [OK]

Hint: Greedy tracks max reachable index in one pass [OK]

Common Mistakes:

• Confusing DP with greedy, thinking recursion is needed

2. Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[ord(c) - ord('a')])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

easy

A. [10]

B. [9, 1]

C. [1, 9]

D. [3, 7]

Solution

1. Step 1: Compute last occurrences

   Characters: e last at 8, c last at 9, b last at 6, d last at 7.

2. Step 2: Trace partitions

   Start=0, end=0 initially. Iterate: - i=0 (e): end=max(0,8)=8 - i=1 (c): end=max(8,9)=9 - i=2 (c): end=9 - i=3 (b): end=max(9,6)=9 - i=4 (b): end=9 - i=5 (b): end=9 - i=6 (b): end=9 - i=7 (d): end=max(9,7)=9 - i=8 (e): end=9 - i=9 (c): i==end, partition size=9-0+1=10 Append 10, start=10 (end of string) But since string length is 10, only one partition of size 10. However, careful: last occurrence of 'e' is 8, 'c' is 9, so partition ends at 9. So only one partition of size 10.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Partition covers entire string length 10 [OK]

Hint: Track max last occurrence to find partition end [OK]

Common Mistakes:

• Miscounting partition size by off-by-one
• Stopping partition too early ignoring max last occurrence
• Confusing character indices

3. Consider the following Python function implementing the optimal wiggle subsequence algorithm. What is the value of count after the loop finishes when the input is [1, 5, 4]?

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace loop iterations

   Input: [1, 5, 4] - i=1: diff=5-1=4 >0 and last_diff=0 ≤0 -> count=2, last_diff=4 - i=2: diff=4-5=-1 <0 and last_diff=4 ≥0 -> count=3, last_diff=-1

2. Step 2: Final count value

   After loop, count=3, which is the length of the longest wiggle subsequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Count increments twice for valid wiggles [OK]

Hint: Count increments on sign change of diff from last_diff

Common Mistakes:

• Off-by-one counting
• Ignoring initial count=1
• Not updating last_diff correctly

4. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

5. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved