Problem

Write a method to sort an array of strings so that all the anagrams are next to each other.

Examples

Example 1

1
2

INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx"
OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx"
Similar Problems

Solution

Below are a few standard approaches. First method (#Method 1 - Brute-force pairwise clustering (bubble-like)) is a naive one, but these approaches are better:

  1. #Method 2 - Group by canonical key (hash map): group strings by a canonical anagram key using a hash table, and
  2. #Method 3 - Sort with precomputed key (stable comparator): sort the array using a precomputed key (anagram-key comparator).

Both produce clusters of anagrams; Method 2 is usually fastest for grouping, while Method 3 can be done in-place if required.

Method 1 - Brute-force pairwise clustering (bubble-like)

Intuition

Compare every pair of strings and swap adjacent strings when they are anagrams, pushing matched anagrams together. This is effectively a bubble-style clustering that requires no extra data structures beyond an anagram test.

Approach

  1. For i from 0 to n-2, for j from i+1 to n-1:
    • If arr[i] and arr[j] are anagrams, swap arr[i+1] and arr[j] to move the match next to arr[i].
  2. Repeat as necessary (the nested loops above suffice to cluster matches around each i).

Complexity

  • ⏰ Time complexity: O(N^2 * K) – we compare O(N^2) pairs and each anagram check can take O(K) time (counting or sorting characters).
  • 🧺 Space complexity: O(1) – in-place swaps and constant additional variables.

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
27
28

#include <string>
#include <vector>

using std::string;
using std::vector;

class Solution {
public:
  static bool areAnagrams(const string &a, const string &b) {
    if (a.size() != b.size()) return false;
    int cnt[26] = {0};
    for (char c : a) ++cnt[c - 'a'];
    for (char c : b) --cnt[c - 'a'];
    for (int v : cnt) if (v != 0) return false;
    return true;
  }

  void sortAnagrams(vector<string>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (areAnagrams(arr[i], arr[j])) {
          std::swap(arr[i + 1], arr[j]);
        }
      }
    }
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package main

type Solution3 struct{}

func areAnagrams(a, b string) bool {
  if len(a) != len(b) { return false }
  var cnt [26]int
  for i := range a { cnt[a[i]-'a']++ }
  for i := range b { cnt[b[i]-'a']-- }
  for _, v := range cnt { if v != 0 { return false } }
  return true
}

func (s *Solution3) sortAnagrams(arr []string) {
  n := len(arr)
  for i := 0; i < n-1; i++ {
    for j := i+1; j < n; j++ {
      if areAnagrams(arr[i], arr[j]) {
        arr[i+1], arr[j] = arr[j], arr[i+1]
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;

public class Solution {
  private static boolean areAnagrams(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] cnt = new int[26];
    for (int i = 0; i < a.length(); ++i) cnt[a.charAt(i)-'a']++;
    for (int i = 0; i < b.length(); ++i) cnt[b.charAt(i)-'a']--;
    for (int v : cnt) if (v != 0) return false;
    return true;
  }

  public void sortAnagrams(String[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; ++i) {
      for (int j = i+1; j < n; ++j) {
        if (areAnagrams(arr[i], arr[j])) {
          String tmp = arr[i+1]; arr[i+1] = arr[j]; arr[j] = tmp;
        }
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  private fun areAnagrams(a: String, b: String): Boolean {
    if (a.length != b.length) return false
    val cnt = IntArray(26)
    for (i in a.indices) cnt[a[i]-'a']++
    for (i in b.indices) cnt[b[i]-'a']--
    for (v in cnt) if (v != 0) return false
    return true
  }

  fun sortAnagrams(arr: Array<String>) {
    val n = arr.size
    for (i in 0 until n-1) {
      for (j in i+1 until n) {
        if (areAnagrams(arr[i], arr[j])) {
          val tmp = arr[i+1]; arr[i+1] = arr[j]; arr[j] = tmp
        }
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from typing import List

class Solution:
  @staticmethod
  def are_anagrams(a: str, b: str) -> bool:
    if len(a) != len(b):
      return False
    cnt = [0]*26
    for ch in a:
      cnt[ord(ch)-ord('a')] += 1
    for ch in b:
      cnt[ord(ch)-ord('a')] -= 1
    return all(v == 0 for v in cnt)

  def sortAnagrams(self, arr: List[str]) -> None:
    n = len(arr)
    for i in range(n-1):
      for j in range(i+1, n):
        if Solution.are_anagrams(arr[i], arr[j]):
          arr[i+1], arr[j] = arr[j], arr[i+1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

pub struct Solution;

impl Solution {
  fn are_anagrams(a: &str, b: &str) -> bool {
    if a.len() != b.len() { return false; }
    let mut cnt = [0i32; 26];
    for ch in a.bytes() { cnt[(ch - b'a') as usize] += 1; }
    for ch in b.bytes() { cnt[(ch - b'a') as usize] -= 1; }
    cnt.iter().all(|&v| v == 0)
  }

  pub fn sort_anagrams(arr: &mut [String]) {
    let n = arr.len();
    for i in 0..n.saturating_sub(1) {
      for j in i+1..n {
        if Solution::are_anagrams(&arr[i], &arr[j]) {
          arr.swap(i+1, j);
        }
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  private static areAnagrams(a: string, b: string): boolean {
    if (a.length !== b.length) return false;
    const cnt = new Array<number>(26).fill(0);
    for (let i = 0; i < a.length; i++) cnt[a.charCodeAt(i)-97]++;
    for (let i = 0; i < b.length; i++) cnt[b.charCodeAt(i)-97]--;
    return cnt.every(v => v === 0);
  }

  sortAnagrams(arr: string[]): void {
    const n = arr.length;
    for (let i = 0; i < n-1; i++) {
      for (let j = i+1; j < n; j++) {
        if (Solution.areAnagrams(arr[i], arr[j])) {
          const tmp = arr[i+1]; arr[i+1] = arr[j]; arr[j] = tmp;
        }
      }
    }
  }
}

Method 2 - Group by canonical key (hash map)

Intuition

Anagrams share the same multiset of characters. Use a canonical representation (sorted characters) as a key and collect original strings into buckets per key. Rewriting the array from these buckets places anagrams next to each other.

Approach

  1. Build a map from key -> list of original strings, where key is the string’s characters sorted.
  2. Record insertion order of keys to keep deterministic grouping (optional).
  3. Overwrite the original array by iterating the map’s buckets and writing each contained string back.

Complexity

  • ⏰ Time complexity: O(N * K log K) – sorting each string of average length K dominates; building and writing buckets is O(N*K).
  • 🧺 Space complexity: O(N * K) – storing the keys and grouped lists requires extra space proportional to total input size.

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
27
28
29

#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>

using std::string;
using std::unordered_map;
using std::vector;

class Solution {
public:
  void sortAnagrams(vector<string>& arr) {
    unordered_map<string, vector<string>> buckets;
    vector<string> order;
    for (auto &s : arr) {
      string key = s;
      std::sort(key.begin(), key.end());
      if (buckets.find(key) == buckets.end())
        order.push_back(key);
      buckets[key].push_back(s);
    }

    int idx = 0;
    for (auto &k : order) {
      for (auto &val : buckets[k])
        arr[idx++] = val;
    }
  }
};
 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

package main

import (
  "sort"
)

type Solution struct{}

func (s *Solution) sortAnagrams(arr []string) {
  buckets := make(map[string][]string)
  order := make([]string, 0, len(arr))
  for _, str := range arr {
    runes := []rune(str)
    sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
    key := string(runes)
    if _, ok := buckets[key]; !ok {
      order = append(order, key)
    }
    buckets[key] = append(buckets[key], str)
  }

  idx := 0
  for _, k := range order {
    for _, v := range buckets[k] {
      arr[idx] = v
      idx++
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;

public class Solution {
  public void sortAnagrams(String[] arr) {
    Map<String, List<String>> buckets = new LinkedHashMap<>();
    for (String s : arr) {
      char[] a = s.toCharArray();
      Arrays.sort(a);
      String key = new String(a);
      buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }

    int idx = 0;
    for (List<String> group : buckets.values()) {
      for (String v : group) {
        arr[idx++] = v;
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  fun sortAnagrams(arr: Array<String>) {
    val buckets = linkedMapOf<String, MutableList<String>>()
    for (s in arr) {
      val key = s.toCharArray().sorted().joinToString(separator = "")
      buckets.computeIfAbsent(key) { mutableListOf() }.add(s)
    }

    var idx = 0
    for (group in buckets.values) {
      for (v in group) {
        arr[idx++] = v
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from typing import List
from collections import OrderedDict

class Solution:
  def sortAnagrams(self, arr: List[str]) -> None:
    buckets: "OrderedDict[str, List[str]]" = OrderedDict()
    for s in arr:
      key = ''.join(sorted(s))
      if key not in buckets:
        buckets[key] = []
      buckets[key].append(s)

    idx = 0
    for group in buckets.values():
      for v in group:
        arr[idx] = v
        idx += 1
 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

use std::collections::HashMap;

pub struct Solution;

impl Solution {
  pub fn sort_anagrams(arr: &mut [String]) {
    let mut buckets: HashMap<String, Vec<String>> = HashMap::new();
    let mut order: Vec<String> = Vec::new();

    for s in arr.iter() {
      let mut chars: Vec<char> = s.chars().collect();
      chars.sort();
      let key: String = chars.into_iter().collect();
      if !buckets.contains_key(&key) {
        order.push(key.clone());
      }
      buckets.entry(key).or_default().push(s.clone());
    }

    let mut idx = 0;
    for k in order.iter() {
      if let Some(group) = buckets.get(k) {
        for v in group.iter() {
          arr[idx] = v.clone();
          idx += 1;
        }
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  sortAnagrams(arr: string[]): void {
    const buckets = new Map<string, string[]>();
    const order: string[] = [];
    for (const s of arr) {
      const key = s.split('').sort().join('');
      if (!buckets.has(key)) order.push(key);
      const list = buckets.get(key) || [];
      list.push(s);
      buckets.set(key, list);
    }

    let idx = 0;
    for (const k of order) {
      const group = buckets.get(k) || [];
      for (const v of group) {
        arr[idx++] = v;
      }
    }
  }
}

Method 3 - Sort with precomputed key (stable comparator)

Intuition

Precompute an anagram key for each string (sorted characters), attach it to the original string, and sort the array by the key. This clusters all strings with identical keys together; using a stable sort preserves relative order within each group.

Approach

  1. Create an array of pairs (key, original_string) where key is the sorted characters of the string.
  2. Sort the pairs by key using the language’s sort routine (stable sort recommended).
  3. Overwrite the original array with the original_string values in sorted order.

Complexity

  • ⏰ Time complexity: O(N * K log K + N log N * K) – sorting characters inside each string costs O(K log K) per string; the sort of N keys costs O(N log N) comparisons and each comparison of keys takes up to O(K).
  • 🧺 Space complexity: O(N * K) – storing the key for each string (pair array) requires extra space proportional to total input.

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

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

using std::pair;
using std::string;
using std::vector;

class Solution {
public:
  void sortAnagrams(vector<string>& arr) {
    vector<pair<string, string>> pairs;
    pairs.reserve(arr.size());
    for (auto &s : arr) {
      string key = s;
      std::sort(key.begin(), key.end());
      pairs.emplace_back(key, s);
    }
    std::sort(pairs.begin(), pairs.end(), [](const pair<string,string>& a, const pair<string,string>& b){
      return a.first < b.first;
    });
    for (size_t i = 0; i < pairs.size(); ++i)
      arr[i] = pairs[i].second;
  }
};
 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

package main

import (
  "sort"
)

type kv struct{
  key string
  val string
}

type Solution2 struct{}

func (s *Solution2) sortAnagrams(arr []string) {
  pairs := make([]kv, 0, len(arr))
  for _, str := range arr {
    runes := []rune(str)
    sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
    pairs = append(pairs, kv{key: string(runes), val: str})
  }
  sort.Slice(pairs, func(i, j int) bool { return pairs[i].key < pairs[j].key })
  for i := range pairs {
    arr[i] = pairs[i].val
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;

public class Solution {
  public void sortAnagrams(String[] arr) {
    int n = arr.length;
    String[][] pairs = new String[n][2];
    for (int i = 0; i < n; ++i) {
      char[] a = arr[i].toCharArray();
      Arrays.sort(a);
      pairs[i][0] = new String(a);
      pairs[i][1] = arr[i];
    }
    Arrays.sort(pairs, new Comparator<String[]>() {
      public int compare(String[] a, String[] b) {
        return a[0].compareTo(b[0]);
      }
    });
    for (int i = 0; i < n; ++i)
      arr[i] = pairs[i][1];
  }
}
1
2
3
4
5
6
7

class Solution {
  fun sortAnagrams(arr: Array<String>) {
    val pairs = arr.map { s -> Pair(s.toCharArray().sorted().joinToString(""), s) }.toMutableList()
    pairs.sortBy { it.first }
    for (i in pairs.indices) arr[i] = pairs[i].second
  }
}
1
2
3
4
5
6
7
8

from typing import List

class Solution:
  def sortAnagrams(self, arr: List[str]) -> None:
    pairs = [ (''.join(sorted(s)), s) for s in arr ]
    pairs.sort()
    for i, (_, v) in enumerate(pairs):
      arr[i] = v
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub struct Solution;

impl Solution {
  pub fn sort_anagrams(arr: &mut [String]) {
    let mut pairs: Vec<(String, String)> = Vec::with_capacity(arr.len());
    for s in arr.iter() {
      let mut chars: Vec<char> = s.chars().collect();
      chars.sort();
      let key: String = chars.into_iter().collect();
      pairs.push((key, s.clone()));
    }
    pairs.sort_by(|a, b| a.0.cmp(&b.0));
    for i in 0..pairs.len() {
      arr[i] = pairs[i].1.clone();
    }
  }
}
1
2
3
4
5
6
7

class Solution {
  sortAnagrams(arr: string[]): void {
    const pairs: [string, string][] = arr.map(s => [s.split('').sort().join(''), s]);
    pairs.sort((a, b) => a[0].localeCompare(b[0]));
    for (let i = 0; i < pairs.length; i++) arr[i] = pairs[i][1];
  }
}