How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at PayPal.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at PayPal during technical interviews.

Minimize a String Using Allowed Swaps | PayPal Coding Question

Q: Minimize a String Using Allowed Swaps

This question evaluates understanding of graph connectivity and constrained string reordering, along with proficiency in applying efficient data structures and algorithms for handling large inputs.

Minimize a String Using Allowed Swaps

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a string `s` of lowercase English letters and an array `pairs`, where each element `pairs[i] = [a, b]` means you may swap the characters at indices `a` and `b`. You may perform any number of swaps, and each allowed pair may be used multiple times. Return the lexicographically smallest string that can be obtained. Indices are zero-based. Example 1: Input: `s = "dcab"`, `pairs = [[0, 3], [1, 2]]` Output: `"bacd"` Example 2: Input: `s = "dcab"`, `pairs = [[0, 3], [1, 2], [0, 2]]` Output: `"abcd"` Constraints: - `1 <= s.length <= 100000` - `0 <= pairs.length <= 100000` - `pairs[i].length == 2` - `0 <= pairs[i][0], pairs[i][1] < s.length`

Quick Answer: This question evaluates understanding of graph connectivity and constrained string reordering, along with proficiency in applying efficient data structures and algorithms for handling large inputs.

You are given a string `s` consisting of lowercase English letters and a list `pairs`, where each element `pairs[i] = [a, b]` means you may swap the characters at indices `a` and `b`. You may perform any number of swaps, and each allowed pair may be used multiple times. Return the lexicographically smallest string that can be obtained after any sequence of valid swaps. Indices are zero-based.

Constraints

1 <= len(s) <= 100000
0 <= len(pairs) <= 100000
pairs[i].length == 2
0 <= pairs[i][0], pairs[i][1] < len(s)

Examples

Input: ('dcab', [[0, 3], [1, 2]])

Expected Output: 'bacd'

Explanation: Indices {0, 3} form one component and {1, 2} form another. Sorting characters within each component gives 'bacd'.

Input: ('dcab', [[0, 3], [1, 2], [0, 2]])

Expected Output: 'abcd'

Explanation: All indices become connected, so the entire string can be rearranged into its lexicographically smallest form.

Input: ('cba', [])

Expected Output: 'cba'

Explanation: No swaps are allowed, so the string cannot change.

Input: ('a', [])

Expected Output: 'a'

Explanation: A single-character string is already minimal.

Input: ('zxyw', [[0, 1], [1, 2], [0, 1]])

Expected Output: 'xyzw'

Explanation: Indices 0, 1, and 2 are connected, even with duplicate pairs. Their characters can be reordered to make the prefix as small as possible.

Input: ('bba', [[0, 2]])

Expected Output: 'abb'

Explanation: Only indices 0 and 2 can swap, so 'b' and 'a' can be reordered to produce 'abb'.

Hints

Think of the indices as nodes in a graph. If two indices are connected directly or indirectly through allowed pairs, their characters can be rearranged among those indices.
For each connected component, collect its indices and characters. Sort the indices and sort the characters, then place the smallest characters into the smallest indices.

Quick Overview

This question evaluates understanding of graph connectivity and constrained string reordering, along with proficiency in applying efficient data structures and algorithms for handling large inputs.