Count Book Line Groups by One Letter Swap
An old book page containsonr or more scrambled lines. Each line contains the same letters, but the letters may appear in different positions.
While restoring the page, an editor can swap two letters in a line. Two lines are connected if they are identical or if one swap can make them equal.
Lines connected directly or through other given lines belong to the same group. Determine the number of separate groups.
Book Line Groups
Implement the following method:
int countLineGroups(List<String> pageLines)
pageLines contains the scrambled lines from the page.- The method returns the number of separate line groups.
Rules
- One swap exchanges the letters at two different positions in a line.
- Identical lines are connected without performing a swap.
- Only lines in
pageLines may connect two lines indirectly.
- Every line belongs to exactly one group.
Constraints
1 ≤ pageLines.size() ≤ 2,0001 ≤ pageLines.get(i).length() ≤ 1,000 pageLines.size() * pageLines.get(i).length() ≤ 20,000 - Every line contains only lowercase English letters.
- All lines have the same length.
- All lines contain the same letters with the same frequencies.
Examples
Example 1
countLineGroups( pageLines = List.of("stop", "spot", "post", "pots", "tops") )
Output: 2
Lines "stop" and "spot" form one group. Lines "post", "pots", and "tops" form another group.
Example 2
countLineGroups( pageLines = List.of("care", "race", "arce", "acre", "acer") )
Output: 1
Every line is connected directly or through another line, so all five lines belong to one group.
Example 3
countLineGroups( pageLines = List.of("abcd", "badc", "cdab") )
Output: 3
No line can become another with one swap, so each line forms its own group.