Reorganize String (No Two Adjacent Same)

🎯

Reorganize String (No Two Adjacent Same)

mediumGREEDYAmazonGoogleFacebook

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

💡 This problem is about rearranging characters so that no two identical ones are adjacent. Beginners often struggle because they try naive rearrangements without considering frequency or the need to separate the most frequent characters carefully.

📋

Problem Statement

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

💡

Example

Input"aab"

Outputaba

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

Input"aaab"

Output

No valid rearrangement exists because 'a' occurs too frequently.

• Single character string → always valid, output same character
• All characters are the same → no valid rearrangement, output empty string
• String with two characters both same → no valid rearrangement, output empty string
• String with two characters different → valid rearrangement is original or swapped

⚠️

Common Mistakes

Not checking if the most frequent character count exceeds (n+1)/2

Returns invalid rearrangement or crashes due to impossible placement

✅ Add a feasibility check before attempting rearrangement

Placing characters without alternating indices leading to adjacent duplicates

Output string has adjacent identical characters, failing problem requirements

✅ Place characters first at even indices, then odd indices to separate duplicates

In heap approach, forgetting to hold back the previously used character

Same character may be placed consecutively, violating constraints

✅ Store previous character and frequency, push back into heap only after placing a different character

Using brute force or generating all permutations for large inputs

Time limit exceeded or program crashes due to combinatorial explosion

✅ Use greedy or heap-based approaches for efficiency

Not handling edge cases like single character or all identical characters

Incorrect output or runtime errors

✅ Add explicit checks and test edge cases thoroughly

🧠

Brute Force (Backtracking / Permutation Generation)

💡 This approach exists to understand the problem deeply by trying all possible rearrangements. It is impractical for large inputs but helps grasp the constraints and why smarter methods are needed.

Intuition

Try every possible permutation of the string and check if any permutation has no two adjacent identical characters.

Algorithm

1. Generate all permutations of the input string.
2. For each permutation, check if any two adjacent characters are the same.
3. If a valid permutation is found, return it immediately.
4. If no valid permutation exists, return an empty string.

💡 The main challenge is generating permutations efficiently and checking adjacency, which is straightforward but computationally expensive.

</>

Code

from itertools import permutations

def reorganizeString(s: str) -> str:
    for perm in permutations(s):
        if all(perm[i] != perm[i+1] for i in range(len(perm)-1)):
            return ''.join(perm)
    return ""

# Driver code
if __name__ == "__main__":
    test_cases = ["aab", "aaab", "abc", "a"]
    for s in test_cases:
        print(f"Input: {s} -> Output: {reorganizeString(s)}")

Line Notes

from itertools import permutationsImport permutations to generate all possible orderings of characters

for perm in permutations(s):Try every possible arrangement of characters

if all(perm[i] != perm[i+1] for i in range(len(perm)-1))Check if no two adjacent characters are the same

return ''.join(perm)Return the first valid permutation found

return ""If no valid permutation exists, return empty string

import java.util.*;

public class ReorganizeString {
    public static String reorganizeString(String s) {
        List<String> permutations = new ArrayList<>();
        permute(s.toCharArray(), 0, permutations);
        for (String perm : permutations) {
            if (isValid(perm)) return perm;
        }
        return "";
    }

    private static void permute(char[] arr, int l, List<String> res) {
        if (l == arr.length) {
            res.add(new String(arr));
            return;
        }
        for (int i = l; i < arr.length; i++) {
            swap(arr, l, i);
            permute(arr, l + 1, res);
            swap(arr, l, i);
        }
    }

    private static boolean isValid(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) return false;
        }
        return true;
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        String[] tests = {"aab", "aaab", "abc", "a"};
        for (String s : tests) {
            System.out.println("Input: " + s + " -> Output: " + reorganizeString(s));
        }
    }
}

Line Notes

permute(char[] arr, int l, List<String> res)Generate all permutations by swapping characters recursively

if (l == arr.length)Base case: one permutation generated, add to results

swap(arr, l, i)Backtrack by swapping back to restore original array

permute(arr, l + 1, res)Recursively generate permutations for next position

isValid(String s)Check if no two adjacent characters are the same

return ""Return empty string if no valid permutation found

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool isValid(const string& s) {
    for (int i = 0; i < (int)s.size() - 1; i++) {
        if (s[i] == s[i + 1]) return false;
    }
    return true;
}

void permute(string& s, int l, vector<string>& res) {
    if (l == (int)s.size()) {
        res.push_back(s);
        return;
    }
    for (int i = l; i < (int)s.size(); i++) {
        swap(s[l], s[i]);
        permute(s, l + 1, res);
        swap(s[l], s[i]);
    }
}

string reorganizeString(string s) {
    vector<string> permutations;
    permute(s, 0, permutations);
    for (auto& perm : permutations) {
        if (isValid(perm)) return perm;
    }
    return "";
}

int main() {
    vector<string> tests = {"aab", "aaab", "abc", "a"};
    for (auto& s : tests) {
        cout << "Input: " << s << " -> Output: " << reorganizeString(s) << endl;
    }
    return 0;
}

Line Notes

void permute(string& s, int l, vector<string>& res)Recursively generate all permutations by swapping characters

if (l == (int)s.size())Base case: add current permutation to results

swap(s[l], s[i])Backtrack by swapping back to restore original string

permute(s, l + 1, res)Recursively generate permutations for next position

isValid(const string& s)Check if no two adjacent characters are the same

return ""Return empty string if no valid permutation found

function reorganizeString(s) {
    const results = [];
    const arr = s.split('');

    function permute(l) {
        if (l === arr.length) {
            results.push(arr.join(''));
            return;
        }
        for (let i = l; i < arr.length; i++) {
            [arr[l], arr[i]] = [arr[i], arr[l]];
            permute(l + 1);
            [arr[l], arr[i]] = [arr[i], arr[l]];
        }
    }

    function isValid(str) {
        for (let i = 0; i < str.length - 1; i++) {
            if (str[i] === str[i + 1]) return false;
        }
        return true;
    }

    permute(0);
    for (const perm of results) {
        if (isValid(perm)) return perm;
    }
    return "";
}

// Test cases
const tests = ["aab", "aaab", "abc", "a"];
tests.forEach(s => console.log(`Input: ${s} -> Output: ${reorganizeString(s)}`));

Line Notes

function permute(l)Generate all permutations recursively by swapping characters

if (l === arr.length)Base case: add current permutation to results

[arr[l], arr[i]] = [arr[i], arr[l]]Backtrack by swapping back to restore original array

permute(l + 1)Recursively generate permutations for next position

function isValid(str)Check if no two adjacent characters are the same

return ""Return empty string if no valid permutation found

⏱

Complexity

TimeO(n! * n)

SpaceO(n! * n)

Generating all permutations is O(n!) and checking adjacency is O(n) per permutation, making this approach infeasible for large n.

💡 For n=10, this means over 3 million permutations, each checked for adjacency, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Greedy Approach Using Sorting and Two Pointers

💡 This approach improves efficiency by sorting characters by frequency and placing the most frequent characters first, then filling gaps with others to avoid adjacency.

Intuition

Sort characters by frequency descending, place the most frequent characters at even indices first, then fill remaining characters in the gaps to avoid adjacency.

Algorithm

1. Count frequency of each character.
2. Sort characters by descending frequency.
3. Place the most frequent characters at even indices (0, 2, 4, ...).
4. Place remaining characters at odd indices (1, 3, 5, ...).
5. If any character frequency is more than (n+1)/2, return empty string.

💡 The key insight is that the most frequent character cannot occupy more than half the string rounded up, or adjacency is unavoidable.

</>

Code

def reorganizeString(s: str) -> str:
    from collections import Counter
    n = len(s)
    freq = Counter(s)
    max_freq = max(freq.values())
    if max_freq > (n + 1) // 2:
        return ""
    sorted_chars = sorted(freq.items(), key=lambda x: -x[1])
    res = [None] * n
    idx = 0
    for ch, count in sorted_chars:
        for _ in range(count):
            res[idx] = ch
            idx += 2
            if idx >= n:
                idx = 1
    return "".join(res)

# Driver code
if __name__ == "__main__":
    tests = ["aab", "aaab", "abc", "a"]
    for s in tests:
        print(f"Input: {s} -> Output: {reorganizeString(s)}")

Line Notes

from collections import CounterUse Counter to efficiently count character frequencies

max_freq = max(freq.values())Find the highest frequency to check feasibility

if max_freq > (n + 1) // 2If any character is too frequent, no valid rearrangement exists

sorted_chars = sorted(freq.items(), key=lambda x: -x[1])Sort characters by descending frequency

res = [None] * nPrepare result array to place characters

idx = 0Start placing characters at even indices

for ch, count in sorted_charsPlace each character count times

if idx >= n: idx = 1Switch to odd indices after filling even positions

import java.util.*;

public class ReorganizeString {
    public static String reorganizeString(String s) {
        int n = s.length();
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        int maxFreq = 0;
        for (int f : freq) maxFreq = Math.max(maxFreq, f);
        if (maxFreq > (n + 1) / 2) return "";

        Character[] chars = new Character[26];
        for (int i = 0; i < 26; i++) chars[i] = (char) (i + 'a');
        Arrays.sort(chars, (a, b) -> freq[b - 'a'] - freq[a - 'a']);

        char[] res = new char[n];
        int idx = 0;
        for (char ch : chars) {
            int count = freq[ch - 'a'];
            for (int i = 0; i < count; i++) {
                if (idx >= n) idx = 1;
                res[idx] = ch;
                idx += 2;
            }
        }
        return new String(res);
    }

    public static void main(String[] args) {
        String[] tests = {"aab", "aaab", "abc", "a"};
        for (String s : tests) {
            System.out.println("Input: " + s + " -> Output: " + reorganizeString(s));
        }
    }
}

Line Notes

int[] freq = new int[26]Frequency array for lowercase letters

if (maxFreq > (n + 1) / 2) return ""Check if rearrangement is possible

Arrays.sort(chars, (a, b) -> freq[b - 'a'] - freq[a - 'a'])Sort characters by descending frequency

char[] res = new char[n]Result array to place characters

int idx = 0Start placing characters at even indices

for (char ch : chars)Iterate over characters sorted by frequency

if (idx >= n) idx = 1Switch from even to odd indices when even positions filled

res[idx] = chPlace character at current index

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string reorganizeString(string s) {
    int n = s.size();
    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;
    int maxFreq = *max_element(freq.begin(), freq.end());
    if (maxFreq > (n + 1) / 2) return "";

    vector<char> chars(26);
    for (int i = 0; i < 26; i++) chars[i] = 'a' + i;
    sort(chars.begin(), chars.end(), [&](char a, char b) {
        return freq[a - 'a'] > freq[b - 'a'];
    });

    string res(n, ' ');
    int idx = 0;
    for (char ch : chars) {
        int count = freq[ch - 'a'];
        for (int i = 0; i < count; i++) {
            if (idx >= n) idx = 1;
            res[idx] = ch;
            idx += 2;
        }
    }
    return res;
}

int main() {
    vector<string> tests = {"aab", "aaab", "abc", "a"};
    for (auto& s : tests) {
        cout << "Input: " << s << " -> Output: " << reorganizeString(s) << endl;
    }
    return 0;
}

Line Notes

vector<int> freq(26, 0)Frequency vector for all lowercase letters

if (maxFreq > (n + 1) / 2) return ""Check feasibility of rearrangement

sort(chars.begin(), chars.end(), ... )Sort characters by descending frequency

string res(n, ' ')Initialize result string with spaces

int idx = 0Start placing characters at even indices

if (idx >= n) idx = 1Switch from even to odd indices after filling even positions

res[idx] = chPlace character at current index

function reorganizeString(s) {
    const n = s.length;
    const freq = new Array(26).fill(0);
    for (const ch of s) freq[ch.charCodeAt(0) - 97]++;
    const maxFreq = Math.max(...freq);
    if (maxFreq > Math.floor((n + 1) / 2)) return "";

    const chars = Array.from({ length: 26 }, (_, i) => String.fromCharCode(i + 97));
    chars.sort((a, b) => freq[b.charCodeAt(0) - 97] - freq[a.charCodeAt(0) - 97]);

    const res = new Array(n);
    let idx = 0;
    for (const ch of chars) {
        let count = freq[ch.charCodeAt(0) - 97];
        for (let i = 0; i < count; i++) {
            if (idx >= n) idx = 1;
            res[idx] = ch;
            idx += 2;
        }
    }
    return res.join('');
}

// Test cases
const tests = ["aab", "aaab", "abc", "a"];
tests.forEach(s => console.log(`Input: ${s} -> Output: ${reorganizeString(s)}`));

Line Notes

const freq = new Array(26).fill(0)Frequency array for lowercase letters

if (maxFreq > Math.floor((n + 1) / 2)) return ""Check if rearrangement is possible

chars.sort((a, b) => freq[b.charCodeAt(0) - 97] - freq[a.charCodeAt(0) - 97])Sort characters by descending frequency

let idx = 0Start placing characters at even indices

if (idx >= n) idx = 1Switch from even to odd indices after filling even positions

res[idx] = chPlace character at current index

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies is O(n), sorting 26 letters is O(1) practically, and placing characters is O(n). Overall efficient for large inputs.

💡 For n=10^5, this approach runs quickly because sorting is on fixed alphabet size and placement is linear.

Interview Verdict: Accepted

This approach is efficient and accepted in interviews; it balances simplicity and performance well.

🧠

Greedy Approach Using Max Heap (Priority Queue)

💡 This approach uses a max heap to always pick the character with the highest remaining frequency, ensuring no two adjacent characters are the same by temporarily holding the last used character.

Intuition

Use a max heap to pick the most frequent character available, append it to the result, then hold it aside until the next character is placed to avoid adjacency.

Algorithm

1. Count frequency of each character.
2. Build a max heap of (frequency, character).
3. Pop the top character and append it to the result.
4. Hold the previously used character aside if it still has remaining frequency.
5. Repeat until heap is empty.
6. If the result length equals input length, return result; else return empty string.

💡 The key is to never reuse the same character immediately by holding it until another character is placed.

</>

Code

import heapq
from collections import Counter

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    max_heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(max_heap)
    prev_count, prev_char = 0, ''
    result = []

    while max_heap:
        count, ch = heapq.heappop(max_heap)
        result.append(ch)
        if prev_count < 0:
            heapq.heappush(max_heap, (prev_count, prev_char))
        prev_count, prev_char = count + 1, ch

    res_str = ''.join(result)
    if len(res_str) != len(s):
        return ""
    return res_str

# Driver code
if __name__ == "__main__":
    tests = ["aab", "aaab", "abc", "a"]
    for s in tests:
        print(f"Input: {s} -> Output: {reorganizeString(s)}")

Line Notes

freq = Counter(s)Count frequency of each character

max_heap = [(-count, ch) for ch, count in freq.items()]Create max heap by negating counts

heapq.heapify(max_heap)Transform list into a heap structure

prev_count, prev_char = 0, ''Track previously used character and its remaining count

while max_heap:Process characters until none left

count, ch = heapq.heappop(max_heap)Pop character with highest frequency

result.append(ch)Append chosen character to result

if prev_count < 0: heapq.heappush(max_heap, (prev_count, prev_char))Push back previous character if still available

prev_count, prev_char = count + 1, chUpdate previous character with decremented count

res_str = ''.join(result)Convert list of characters to string

if len(res_str) != len(s)Check if rearrangement is complete and valid

import java.util.*;

public class ReorganizeString {
    public static String reorganizeString(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (freq[i] > 0) maxHeap.offer(new int[]{freq[i], i});
        }

        StringBuilder result = new StringBuilder();
        int[] prev = {0, -1}; // frequency, char index

        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            result.append((char) (curr[1] + 'a'));
            curr[0]--;
            if (prev[0] > 0) maxHeap.offer(prev);
            prev = curr;
        }

        if (result.length() != s.length()) return "";
        return result.toString();
    }

    public static void main(String[] args) {
        String[] tests = {"aab", "aaab", "abc", "a"};
        for (String s : tests) {
            System.out.println("Input: " + s + " -> Output: " + reorganizeString(s));
        }
    }
}

Line Notes

int[] freq = new int[26]Frequency array for characters

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0])Max heap based on frequency

if (freq[i] > 0) maxHeap.offer(new int[]{freq[i], i})Add characters with positive frequency

StringBuilder result = new StringBuilder()Build result string efficiently

int[] prev = {0, -1}Track previously used character and remaining frequency

while (!maxHeap.isEmpty())Process characters until heap is empty

int[] curr = maxHeap.poll()Pop character with highest frequency

result.append((char) (curr[1] + 'a'))Append character to result

curr[0]--Decrement frequency after use

if (prev[0] > 0) maxHeap.offer(prev)Push back previous character if still available

prev = currUpdate previous character to current

if (result.length() != s.length()) return ""Check if rearrangement is valid

#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;

string reorganizeString(string s) {
    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;

    priority_queue<pair<int, char>> maxHeap;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) maxHeap.push({freq[i], (char)(i + 'a')});
    }

    string result;
    pair<int, char> prev = {0, '#'};

    while (!maxHeap.empty()) {
        auto curr = maxHeap.top(); maxHeap.pop();
        result += curr.second;
        curr.first--;
        if (prev.first > 0) maxHeap.push(prev);
        prev = curr;
    }

    if ((int)result.size() != (int)s.size()) return "";
    return result;
}

int main() {
    vector<string> tests = {"aab", "aaab", "abc", "a"};
    for (auto& s : tests) {
        cout << "Input: " << s << " -> Output: " << reorganizeString(s) << endl;
    }
    return 0;
}

Line Notes

vector<int> freq(26, 0)Frequency vector for characters

priority_queue<pair<int, char>> maxHeapMax heap storing frequency and character

if (freq[i] > 0) maxHeap.push(...)Add characters with positive frequency

string resultBuild result string

pair<int, char> prev = {0, '#'}Track previously used character and remaining frequency

while (!maxHeap.empty())Process characters until heap is empty

auto curr = maxHeap.top(); maxHeap.pop()Pop character with highest frequency

result += curr.secondAppend character to result

curr.first--Decrement frequency after use

if (prev.first > 0) maxHeap.push(prev)Push back previous character if still available

prev = currUpdate previous character to current

if ((int)result.size() != (int)s.size()) return ""Check if rearrangement is valid

function reorganizeString(s) {
    const freq = new Array(26).fill(0);
    for (const ch of s) freq[ch.charCodeAt(0) - 97]++;

    const maxHeap = [];
    for (let i = 0; i < 26; i++) {
        if (freq[i] > 0) maxHeap.push([freq[i], String.fromCharCode(i + 97)]);
    }
    maxHeap.sort((a, b) => b[0] - a[0]);

    const result = [];
    let prev = [0, ''];

    while (maxHeap.length > 0) {
        const [count, ch] = maxHeap.shift();
        result.push(ch);
        if (prev[0] > 0) {
            maxHeap.push(prev);
            maxHeap.sort((a, b) => b[0] - a[0]);
        }
        prev = [count - 1, ch];
    }

    const resStr = result.join('');
    return resStr.length === s.length ? resStr : "";
}

// Test cases
const tests = ["aab", "aaab", "abc", "a"];
tests.forEach(s => console.log(`Input: ${s} -> Output: ${reorganizeString(s)}`));

Line Notes

const freq = new Array(26).fill(0)Frequency array for characters

for (const ch of s) freq[ch.charCodeAt(0) - 97]++Count frequency of each character

const maxHeap = []Initialize array to simulate max heap

if (freq[i] > 0) maxHeap.push([freq[i], String.fromCharCode(i + 97)])Add characters with positive frequency

maxHeap.sort((a, b) => b[0] - a[0])Sort heap to simulate max heap behavior

const result = []Build result array

let prev = [0, '']Track previously used character and remaining frequency

while (maxHeap.length > 0)Process characters until heap is empty

const [count, ch] = maxHeap.shift()Pop character with highest frequency

result.push(ch)Append character to result

if (prev[0] > 0)Push back previously used character if still available

prev = [count - 1, ch]Update previous character with decremented count

const resStr = result.join('')Convert result array to string

return resStr.length === s.length ? resStr : ""Return result if valid, else empty string

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Where k is the number of unique characters (up to 26). Each character is pushed and popped from the heap multiple times, each heap operation is O(log k).

💡 For English lowercase letters, k=26, so heap operations are very fast, making this approach efficient for large inputs.

Interview Verdict: Accepted

This is the optimal greedy approach using a heap, commonly expected in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the heap-based greedy approach for optimal balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Sorting + Two Pointers	O(n log n)	O(n)	No	Yes	Good alternative if heap not allowed
3. Greedy Max Heap	O(n log k)	O(k)	No	Yes	Optimal approach to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss the greedy approach using sorting and two pointers.Step 4: Present the optimal heap-based greedy approach.Step 5: Code the heap-based approach and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify greedy patterns, handle edge cases, and implement efficient data structures like heaps.

Common Follow-ups

• What if the input contains uppercase letters or other characters? → Extend frequency array or map accordingly.
• Can you generalize this to avoid k adjacent characters? → Use a similar heap approach with k-1 holding buffer.

💡 These follow-ups test your ability to generalize and adapt your solution beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Need to rearrange characters to avoid adjacency; 2) Frequency counts matter; 3) Greedy selection of most frequent elements; 4) Use of heap or sorting to manage frequencies.

Signature Phrases

no two adjacent characters are the samerearrange stringfrequency of characters

NOT This Pattern When

Problems that require exact order preservation or dynamic programming for subsequence counts are different.

Similar Problems

Task Scheduler - scheduling tasks with cooldowns to avoid adjacencyRearrange String k Distance Apart - generalizes adjacency constraint to distance k

Practice

1. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?

easy

A. 534330

B. 53430

C. 534303

D. 534330

Solution

1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

   We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

   Concatenate to get '534330'. The check for leading zero is false since first is '5'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation order matches expected largest number [OK]

Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]

Common Mistakes:

• Off-by-one in sorting
• Ignoring leading zero case
• Misordering '30' and '3'

2. You have two arrays representing the top and bottom halves of dominoes. You want to make all values in one row uniform by rotating some dominoes. Which algorithmic approach guarantees an optimal solution with minimal rotations?

easy

A. Dynamic Programming that tries all possible uniform values and stores intermediate results

B. Greedy approach checking only the two candidate values from the first domino

C. Backtracking to try all rotation combinations exhaustively

D. Sorting both arrays and then matching values to minimize rotations

Solution

1. Step 1: Identify candidate values from the first domino

   The only possible uniform values are the top or bottom value of the first domino, since all dominoes must match one of these.

2. Step 2: Check feasibility and count rotations

   For each candidate, verify if all dominoes can be rotated to match it and count minimal rotations needed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking only two candidates reduces complexity and guarantees correctness [OK]

Hint: Only two candidates from first domino suffice [OK]

Common Mistakes:

• Trying all numbers 1-6 unnecessarily
• Using DP or backtracking wasting time

3. You have 2n people and need to send exactly n to city A and n to city B. Each person has a different cost for each city. Which approach guarantees the minimum total cost for sending exactly half to each city?

easy

A. Dynamic programming that tries all subsets of people for city A and city B

B. Greedy algorithm sorting people by the difference in their costs between the two cities and assigning the first half to city A and the rest to city B

C. Greedy algorithm sorting people by their absolute cost to city A and assigning the cheapest to city A until full

D. Brute force recursion without memoization to try all assignments

Solution

1. Step 1: Understand problem constraints

   We must send exactly n people to city A and n to city B, minimizing total cost.

2. Step 2: Why sorting by cost difference works

   Sorting by cost difference (cost to A minus cost to B) prioritizes sending people who are cheaper to city A first, and those cheaper to city B later, ensuring minimal total cost.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting by difference balances assignments optimally [OK]

Hint: Sort by cost difference to assign optimally [OK]

Common Mistakes:

• Sorting by absolute cost to one city ignores balance constraint
• Brute force without memoization is too slow
• DP over subsets is correct but inefficient

4. Examine the following BFS-based code for Jump Game II. Which line contains a subtle bug that can cause incorrect jump counts or infinite loops?

medium

A. Line checking if next_pos == n - 1 to return jumps

B. Line incrementing jumps before processing current level

C. Line calculating furthest_jump without bounding by n-1

D. Line adding next_pos to visited set

Solution

1. Step 1: Identify furthest_jump calculation

   furthest_jump = pos + nums[pos] can exceed array bounds, causing range() to go out of range or runtime error.

2. Step 2: Check impact

   Without min(pos + nums[pos], n - 1), code may attempt invalid indices, causing incorrect behavior or crashes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bounding furthest_jump by n-1 prevents out-of-range errors [OK]

Hint: Always bound jump indices within array length [OK]

Common Mistakes:

• Forgetting to limit furthest_jump to n-1
• Incrementing jumps incorrectly
• Missing visited set usage

5. Suppose the Jump Game problem is modified so that you can jump backward as well as forward (i.e., jumps can be negative or positive). Which of the following approaches correctly determines if you can reach the last index from the first index under this new constraint?

hard

A. Use the original greedy approach tracking max reachable index, ignoring backward jumps

B. Use a breadth-first search (BFS) or graph traversal to explore all reachable indices including backward jumps

C. Use dynamic programming with memoization to recursively check reachability from each index

D. Sort the array and apply binary search to find reachable indices efficiently

Solution

1. Step 1: Understand the impact of backward jumps

   Backward jumps mean the problem is no longer monotonic; maxReach tracking fails as reachable indices can decrease.

2. Step 2: Identify suitable approach

   BFS or graph traversal explores all reachable indices in any direction, correctly handling negative jumps.

3. Step 3: Explain why other options fail

   Greedy fails due to backward jumps; DP recursion is possible but less efficient; sorting is irrelevant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS explores all reachable nodes regardless of jump direction [OK]

Hint: Backward jumps break greedy; BFS needed to explore all reachable indices [OK]

Common Mistakes:

• Trying to apply greedy despite backward jumps
• Assuming sorting helps reachability