Largest String With Swaps

Problem

Given a string s of length N and a list of allowed index swaps (pairs of indices where characters may be swapped any number of times), produce the lexicographically largest string obtainable by applying any sequence of the allowed swaps.

Intuition: allowed swaps define an undirected graph over indices; any indices in the same connected component can permute their characters arbitrarily. So for each connected component, collect its characters, sort them in descending order, and place the largest available characters into the component’s indices in ascending index order.

Examples

Example 1

1
2


Input: s = "abdc", swaps = [(0,3),(2,3)]
Output: "dbca"

Example 2

1
2


Input: s = "acxrabdz", swaps = [(0,2),(5,7),(7,2),(1,6)]
Output: "zxrdcbaa"

Solution

We describe two equivalent approaches that differ only in how the characters for each component are stored and retrieved.

Method 1 — Disjoint set (union-find) + sort

Approach

Build a disjoint-set union (DSU) of indices using the allowed swaps.
For each index i, find its component root r = find(i) and append s[i] to the list for component r.
For every component list, sort characters in descending order (or ascending and pop from the end).
Reconstruct the answer by iterating indices i = 0..N-1 and taking the next largest character from component find(i).

This is O(N log N) due to sorting the characters within components and uses O(N) extra memory.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <bits/stdc++.h>
using namespace std;

struct DSU {
  vector<int> p;
  DSU(int n): p(n){ iota(p.begin(), p.end(), 0); }
  int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
  void unite(int a,int b){ a=find(a); b=find(b); if(a!=b) p[b]=a; }
};

string largestStringWithSwaps(string s, vector<pair<int,int>> swaps){
  int n = s.size();
  DSU dsu(n);
  for(auto &pr: swaps) dsu.unite(pr.first, pr.second);
  unordered_map<int, vector<char>> groups;
  for(int i=0;i<n;++i) groups[dsu.find(i)].push_back(s[i]);
  for(auto &kv: groups) sort(kv.second.begin(), kv.second.end()); // ascending
  string ans; ans.reserve(n);
  unordered_map<int,int> idx; // pointer to next largest (from back)
  for(int i=0;i<n;++i){
    auto &v = groups[dsu.find(i)];
    ans.push_back(v.back());
    v.pop_back();
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


package main

import (
  "sort"
)

type DSU struct{p []int}
func NewDSU(n int) *DSU { d:=&DSU{p:make([]int,n)}; for i:=0;i<n;i++{d.p[i]=i}; return d }
func (d *DSU) Find(x int) int { if d.p[x]==x { return x }; d.p[x]=d.Find(d.p[x]); return d.p[x] }
func (d *DSU) Unite(a,b int) { a=d.Find(a); b=d.Find(b); if a!=b { d.p[b]=a } }

func largestStringWithSwaps(s string, swaps [][2]int) string {
  n := len(s)
  d := NewDSU(n)
  for _, p := range swaps { d.Unite(p[0], p[1]) }
  groups := map[int][]rune{}
  for i, r := range []rune(s) { groups[d.Find(i)] = append(groups[d.Find(i)], r) }
  for k := range groups { sort.Slice(groups[k], func(i,j int) bool { return groups[k][i] < groups[k][j] }) }
  res := make([]rune, n)
  ptr := map[int]int{}
  for i := 0; i < n; i++ {
    g := d.Find(i)
    v := groups[g]
    res[i] = v[len(v)-1-ptr[g]]
    ptr[g]++
  }
  return string(res)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import java.util.*;

class Solution {
  static class DSU {
    int[] p;
    DSU(int n){ p=new int[n]; for(int i=0;i<n;i++) p[i]=i; }
    int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
    void unite(int a,int b){ a=find(a); b=find(b); if(a!=b) p[b]=a; }
  }

  public String largestStringWithSwaps(String s, List<int[]> swaps){
    int n=s.length(); DSU d=new DSU(n);
    for(int[] r: swaps) d.unite(r[0], r[1]);
    Map<Integer, List<Character>> groups=new HashMap<>();
    for(int i=0;i<n;i++) groups.computeIfAbsent(d.find(i), k->new ArrayList<>()).add(s.charAt(i));
    for(List<Character> lst: groups.values()) Collections.sort(lst);
    StringBuilder sb=new StringBuilder();
    for(int i=0;i<n;i++){
      List<Character> lst=groups.get(d.find(i));
      sb.append(lst.remove(lst.size()-1));
    }
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
  class DSU(n:Int){
    val p = IntArray(n){it}
    fun find(x:Int):Int = if(p[x]==x) x else { p[x]=find(p[x]); p[x] }
    fun unite(a:Int,b:Int){ val x=find(a); val y=find(b); if(x!=y) p[y]=x }
  }

  fun largestStringWithSwaps(s:String, swaps: List<IntArray>): String {
    val n = s.length
    val d = DSU(n)
    for (p in swaps) d.unite(p[0], p[1])
    val groups = mutableMapOf<Int, MutableList<Char>>()
    for (i in 0 until n) groups.getOrPut(d.find(i)) { mutableListOf() }.add(s[i])
    for (lst in groups.values) lst.sort()
    val sb = StringBuilder()
    for (i in 0 until n) sb.append(groups[d.find(i)]!!.removeAt(groups[d.find(i)]!!.size-1))
    return sb.toString()
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


from collections import defaultdict

class DSU:
    def __init__(self,n):
        self.p=list(range(n))
    def find(self,a):
        if self.p[a]!=a: self.p[a]=self.find(self.p[a])
        return self.p[a]
    def unite(self,a,b):
        a=self.find(a); b=self.find(b)
        if a!=b: self.p[b]=a

def largestStringWithSwaps(s: str, swaps: list[tuple[int,int]]) -> str:
    n=len(s)
    d=DSU(n)
    for a,b in swaps: d.unite(a,b)
    groups=defaultdict(list)
    for i,ch in enumerate(s): groups[d.find(i)].append(ch)
    for k in groups: groups[k].sort()
    res=[]
    for i in range(n):
        grp=groups[d.find(i)]
        res.append(grp.pop())
    return ''.join(res)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


use std::collections::BTreeMap;

struct DSU{p:Vec<usize>}
impl DSU{fn new(n:usize)->Self{let mut p=vec![0;n]; for i in 0..n{p[i]=i} Self{p}} fn find(&mut self,x:usize)->usize{ if self.p[x]==x {x} else { let r=self.find(self.p[x]); self.p[x]=r; r } } fn unite(&mut self,a:usize,b:usize){ let x=self.find(a); let y=self.find(b); if x!=y { self.p[y]=x } }}

fn largestStringWithSwaps(s: &str, swaps: &[(usize,usize)]) -> String {
    let n = s.len();
    let mut d = DSU::new(n);
    for &(a,b) in swaps { d.unite(a,b); }
    let mut groups: BTreeMap<usize, Vec<char>> = BTreeMap::new();
    for (i,ch) in s.chars().enumerate() { groups.entry(d.find(i)).or_default().push(ch); }
    for (_k,v) in groups.iter_mut() { v.sort(); }
    let mut ans = String::with_capacity(n);
    for i in 0..n { let g = d.find(i); let v = groups.get_mut(&g).unwrap(); ans.push(v.pop().unwrap()); }
    ans
}

Complexity

Time: O(N log N) overall (sorting characters per component dominates).
Space: O(N) auxiliary.

Method 2 — DSU + priority queue (memory/time trade)

Use a max-heap per component (priority queue ordered descending). Insert each character into its component heap, then reconstruct by polling the heap for each index. This avoids explicit per-component sort and is convenient when a language provides a PQ implementation.

Intuition

A priority queue per component always yields the currently largest available character in that component. By inserting all characters of a component into a max-heap, polling the heap gives characters in descending order without a separate sorting step.

Approach

Build a DSU of indices from swaps.
For each index i, compute r = find(i) and push s[i] into the max-heap for component r.
Reconstruct the answer by iterating i = 0..N-1 and appending heap_for(find(i)).poll().

Edge cases: validate swaps indices are within [0, N); handle empty string by returning "".

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#include <bits/stdc++.h>
using namespace std;

struct DSU { vector<int> p; DSU(int n):p(n){ iota(p.begin(),p.end(),0);} int find(int x){ return p[x]==x?x:p[x]=find(p[x]); } void unite(int a,int b){ a=find(a); b=find(b); if(a!=b) p[b]=a; } };

string largestStringWithSwaps(string s, const vector<pair<int,int>>& swaps){
  int n = s.size();
  DSU dsu(n);
  for(auto &pr: swaps) dsu.unite(pr.first, pr.second);
  unordered_map<int, priority_queue<char>> groups;
  for(int i=0;i<n;++i) groups[dsu.find(i)].push(s[i]);
  string ans; ans.reserve(n);
  for(int i=0;i<n;++i){ auto &pq = groups[dsu.find(i)]; ans.push_back(pq.top()); pq.pop(); }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


package main

import (
  "container/heap"
)

type RuneHeap []rune
func (h RuneHeap) Len() int { return len(h) }
func (h RuneHeap) Less(i,j int) bool { return h[i] > h[j] } // max-heap
func (h RuneHeap) Swap(i,j int) { h[i],h[j] = h[j],h[i] }
func (h *RuneHeap) Push(x interface{}) { *h = append(*h, x.(rune)) }
func (h *RuneHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type DSU struct{ p []int }
func NewDSU(n int) *DSU { d:=&DSU{p:make([]int,n)}; for i:=0;i<n;i++{d.p[i]=i}; return d }
func (d *DSU) Find(x int) int { if d.p[x]==x { return x }; d.p[x]=d.Find(d.p[x]); return d.p[x] }
func (d *DSU) Unite(a,b int) { a=d.Find(a); b=d.Find(b); if a!=b { d.p[b]=a } }

func largestStringWithSwaps(s string, swaps [][2]int) string {
  n := len(s)
  if n==0 { return "" }
  d := NewDSU(n)
  for _, p := range swaps { d.Unite(p[0], p[1]) }
  groups := map[int]*RuneHeap{}
  for i, r := range []rune(s) {
    g := d.Find(i)
    if groups[g] == nil { h := &RuneHeap{}; heap.Init(h); groups[g]=h }
    heap.Push(groups[g], r)
  }
  res := make([]rune, n)
  for i := 0; i < n; i++ { g := d.Find(i); res[i] = heap.Pop(groups[g]).(rune) }
  return string(res)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import java.util.*;

class Solution {
  static class DSU { int[] p; DSU(int n){ p=new int[n]; for(int i=0;i<n;i++) p[i]=i; } int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); } void unite(int a,int b){ a=find(a); b=find(b); if(a!=b) p[b]=a; } }

  public String largestStringWithSwaps(String s, List<int[]> swaps){
    int n = s.length(); if (n==0) return "";
    DSU d = new DSU(n);
    for(int[] r: swaps) d.unite(r[0], r[1]);
    Map<Integer, PriorityQueue<Character>> groups = new HashMap<>();
    for(int i=0;i<n;i++){
      int g = d.find(i);
      groups.computeIfAbsent(g, k->new PriorityQueue<>(Comparator.reverseOrder())).offer(s.charAt(i));
    }
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<n;i++) sb.append(groups.get(d.find(i)).poll());
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


import java.util.PriorityQueue

class Solution {
  class DSU(n:Int){ val p = IntArray(n){it}; fun find(x:Int):Int = if(p[x]==x) x else { p[x]=find(p[x]); p[x] }; fun unite(a:Int,b:Int){ val x=find(a); val y=find(b); if(x!=y) p[y]=x } }

  fun largestStringWithSwaps(s:String, swaps: List<IntArray>): String {
    val n = s.length
    if (n==0) return ""
    val d = DSU(n)
    for (p in swaps) d.unite(p[0], p[1])
    val groups = mutableMapOf<Int, PriorityQueue<Char>>()
    for (i in 0 until n) {
      val g = d.find(i)
      groups.computeIfAbsent(g) { PriorityQueue<Char>(compareByDescending { it }) }.add(s[i])
    }
    val sb = StringBuilder()
    for (i in 0 until n) sb.append(groups[d.find(i)]!!.poll())
    return sb.toString()
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


import heapq
from collections import defaultdict

class DSU:
    def __init__(self,n): self.p=list(range(n))
    def find(self,a):
        if self.p[a]!=a: self.p[a]=self.find(self.p[a])
        return self.p[a]
    def unite(self,a,b):
        a=self.find(a); b=self.find(b)
        if a!=b: self.p[b]=a

def largestStringWithSwaps(s: str, swaps: list[tuple[int,int]]) -> str:
    n = len(s)
    if n == 0: return ""
    d = DSU(n)
    for a,b in swaps: d.unite(a,b)
    groups = defaultdict(list)
    for i,ch in enumerate(s):
        g = d.find(i)
        # use min-heap of negative ord to simulate max-heap
        heapq.heappush(groups[g], (-ord(ch), ch))
    res = []
    for i in range(n): res.append(heapq.heappop(groups[d.find(i)])[1])
    return ''.join(res)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


use std::collections::{HashMap, BinaryHeap};

struct DSU{p:Vec<usize>}
impl DSU{fn new(n:usize)->Self{let mut p=vec![0;n]; for i in 0..n{p[i]=i} Self{p}} fn find(&mut self,x:usize)->usize{ if self.p[x]==x {x} else { let r=self.find(self.p[x]); self.p[x]=r; r } } fn unite(&mut self,a:usize,b:usize){ let x=self.find(a); let y=self.find(b); if x!=y { self.p[y]=x } }}

fn largestStringWithSwaps(s: &str, swaps: &[(usize,usize)]) -> String {
    let n = s.len(); if n==0 { return String::new(); }
    let mut d = DSU::new(n);
    for &(a,b) in swaps { d.unite(a,b); }
    let mut groups: HashMap<usize, BinaryHeap<char>> = HashMap::new();
    for (i,ch) in s.chars().enumerate() { groups.entry(d.find(i)).or_default().push(ch); }
    let mut ans = String::with_capacity(n);
    for i in 0..n { let g = d.find(i); let heap = groups.get_mut(&g).unwrap(); ans.push(heap.pop().unwrap()); }
    ans
}

Complexity

⏰ Time complexity: O(N log K) where K is size of the largest component — inserting N characters into per-component heaps costs O(N log K) in total and each poll costs O(log K); overall dominated by heap operations and is comparable to sorting when summed across components.
🧺 Space complexity: O(N) to store characters in the heaps plus O(N) for DSU structures.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 — Disjoint set (union-find) + sort#

Approach#

Code#

Complexity#

Method 2 — DSU + priority queue (memory/time trade)#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 — Disjoint set (union-find) + sort

Approach

Code

Complexity

Method 2 — DSU + priority queue (memory/time trade)

Intuition

Approach

Code

Complexity