Untitled

import Foundation

// Helper function to check if two strings are similar
func areSimilar(_ s1: String, _ s2: String) -> Bool {
    if s1 == s2 { return true }
    
    var diffIndices = [Int]()
    let chars1 = Array(s1)
    let chars2 = Array(s2)
    
    for i in 0..<chars1.count {
        if chars1[i] != chars2[i] {
            diffIndices.append(i)
        }
        if diffIndices.count > 2 {
            return false
        }
    }
    
    return diffIndices.count == 2 && chars1[diffIndices[0]] == chars2[diffIndices[1]] && chars1[diffIndices[1]] == chars2[diffIndices[0]]
}

// Main function to find the number of groups
func numSimilarGroups(_ strs: [String]) -> Int {
    let n = strs.count
    var adjacencyList = [Int: [Int]]()
    
    // Build the adjacency list
    for i in 0..<n {
        for j in i + 1..<n {
            if areSimilar(strs[i], strs[j]) {
                adjacencyList[i, default: []].append(j)
                adjacencyList[j, default: []].append(i)
            }
        }
    }
    
    var visited = Array(repeating: false, count: n)
    var groups = 0
    
    // Depth-First Search (DFS)
    func dfs(_ node: Int) {
        visited[node] = true
        for neighbor in adjacencyList[node, default: []] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
    
    // Find all connected components
    for i in 0..<n {
        if !visited[i] {
            groups += 1
            dfs(i)
        }
    }
    
    return groups
}

// Test cases
let testCases = [
    ["tars", "rats", "arts", "star"],
    ["omv", "ovm"],
    ["abc", "bca", "cab", "xyz"]
]

for (index, testCase) in testCases.enumerated() {
    print("Test Case \(index + 1): \(numSimilarGroups(testCase))")
}