What is the brute force approach and complexity for Similar String Groups?

Repeat passes over the groups, merging any two groups that have a similar pair across them with time complexity O(N³ · L) and space complexity O(N).

What is the optimal approach and complexity for Similar String Groups?

Check each pair of words once; union the similar ones and count the groups left with optimal time complexity O(N² · L) and space complexity O(N).

How do you identify the pattern for Similar String Groups?

Look for key signals in the prompt: "similar: equal, or one swap apart" indicates An edge between two words. The test is pairwise, so every pair has to be considered.; "the number of groups" indicates Count the DSU sets: start at N and subtract one per successful union.; "all words are anagrams of each other" indicates Equal letters are not enough. Only the pattern of positions decides similarity..

Similar String Groups

Hard·LeetCode #839 Pro OnlyInterview-Level

LeetCode

Problem Statement

You get a list of words. Every word has the same length, and every word is an anagram of the others, so they all use the same letters.

Two words are similar when they are equal, or when swapping one pair of letters in one of them turns it into the other. Similar words are linked, and a group is a set of words that can reach each other through similar pairs. A word that is similar to nothing is a group on its own.

Return the number of groups.

Input

strs: a list of words.

Output

The number of groups.

Example 1

Input: strs = ["tars", "rats", "arts", "star"]

Output: 2

tars and rats are similar, and rats and arts are similar, so those three form one group. star is not similar to any of them, so it is a second group.

Example 2

Input: strs = ["omv", "ovm"]

Output: 1

Swapping the last two letters of omv gives ovm, so they are similar.

Example 3

Input: strs = ["abc", "bca", "cab"]

Output: 3

All three are anagrams, but every pair differs in three positions. No pair is similar, so each word is its own group.

Example 4

Input: strs = ["acb", "abc", "bac"]

Output: 1

acb and bac are not similar to each other, but both are similar to abc. The chain through abc puts all three in one group.

Constraints

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only
• All words in strs have the same length and are anagrams of each other

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“similar: equal, or one swap apart”

→ An edge between two words. The test is pairwise, so every pair has to be considered.

“the number of groups”

→ Count the DSU sets: start at N and subtract one per successful union.

“all words are anagrams of each other”

→ Equal letters are not enough. Only the pattern of positions decides similarity.

Approach Complexity Ladder

Brute Force — merge groups in passes until nothing changesO(N³ · L)O(N)

Repeat passes over the groups, merging any two groups that have a similar pair across them

Optimal — union every similar pairO(N² · L)O(N)

Check each pair of words once; union the similar ones and count the groups left

Brute Force Intuition

Start with one group per word. Each pass compares pairs of groups, and merges two groups when some word in one is similar to some word in the other. Stop when a full pass merges nothing. The number of groups left is the answer.

Recognition rule for this sub-pattern:

"a equals b", "same owner", "can swap" — union them, then process each group together.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture