FastPrep
Problem

Count Similar String Groups

AmazonINTERNONSITE INTERVIEW
See Amazon hiring insights

You are given an array of strings strs. All strings are anagrams of each other.

Two strings are considered similar if they are identical, or if you can make them equal by swapping exactly two characters in one of the strings.

Similarity is transitive: if string a is similar to b, and b is similar to c, then all three belong to the same group.

Return the number of groups of similar strings.

Examples
01 · Example 1
strs = ["tars", "rats", "arts", "star"]
return = 2

"tars" is similar to "rats", and "rats" is similar to "arts", so they form one group. "star" forms another group.

02 · Example 2
strs = ["omv", "ovm"]
return = 1

The two strings differ in exactly two positions, so one swap makes them equal.

Constraints
  • All strings in strs are anagrams of each other.
  • All strings have the same length.
More Amazon problems
drafts saved locally
public int countSimilarStringGroups(String[] strs) {
  // write your code here
}
strs["tars", "rats", "arts", "star"]
expected2
sign in to submit