FastPrep
Problem

Count Similar String Groups

Learn this problem
Amazon logoAmazonINTERNONSITE INTERVIEW
See Amazon hiring insights

Problem statement

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.

Function

countSimilarStringGroups(strs: String[]) → int

Examples

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.

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
checking account