Smallest String With Swaps

MediumGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s of lowercase letters and an array pairs, where each pairs[i] = [a, b] names two indices of s (0-indexed). You may swap the characters at the indices of any listed pair, as many times as you like and in any order. Return the lexicographically smallest string you can produce. Pairs may repeat, and a pair may name the same index twice (such a pair does nothing).

Examples

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Swap indices 0 and 3 to get `"bcad"`, then indices 1 and 2 to get `"bacd"`.
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
All four indices are linked, so the letters can be fully sorted into `"abcd"`.

Constraints

  • 1 <= s.length <= 10^5
  • 0 <= pairs.length <= 10^5
  • 0 <= pairs[i][0], pairs[i][1] < s.length
  • `s` contains only lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems