LeetCode in Kotlin

3999. Minimum Number of String Groups Through Transformations

Hard

You are given an array of strings words.

Define a transformation on a string s as follows:

Two strings are equivalent if one can be transformed into the other by a single transformation.

Partition words into the minimum number of groups such that:

Return an integer denoting the minimum number of groups.

Example 1:

Input: words = [“ntgwz”,”zwntg”]

Output: 1

Explanation:

Example 2:

Input: words = [“abc”,”cab”,”bac”,”acb”,”bca”,”cba”]

Output: 3

Explanation:

The strings can be partitioned into the following groups:

Example 3:

Input: words = [“leet”,”abb”,”bab”,”deed”,”edde”,”code”,”bba”]

Output: 5

Explanation:

The strings can be partitioned into the following groups:

All pairs of strings in each group are equivalent.

Constraints:

Solution

import kotlin.math.min

class Solution {
    fun minimumGroups(words: Array<String>): Int {
        val set = HashSet<Long?>()
        for (w in words) {
            val n = w.length
            val evenLen = (n + 1) shr 1
            val oddLen = n shr 1
            val even = CharArray(evenLen)
            val odd = CharArray(oddLen)
            var ei = 0
            var oi = 0
            for (i in 0..<n) {
                if ((i and 1) == 0) {
                    even[ei++] = w[i]
                } else {
                    odd[oi++] = w[i]
                }
            }
            val eStart = booth(even)
            val oStart = booth(odd)
            val h1 = hash(even, eStart)
            val h2 = hash(odd, oStart)
            val key = h1 * 1000003L + h2
            set.add(key)
        }
        return set.size
    }

    private fun booth(s: CharArray): Int {
        val n = s.size
        if (n <= 1) {
            return 0
        }
        var i = 0
        var j = 1
        var k = 0
        while (i < n && j < n && k < n) {
            val a = s[(i + k) % n]
            val b = s[(j + k) % n]
            if (a == b) {
                k++
            } else if (a > b) {
                i += k + 1
                if (i <= j) {
                    i = j + 1
                }
                k = 0
            } else {
                j += k + 1
                if (j <= i) {
                    j = i + 1
                }
                k = 0
            }
        }
        return min(i, j)
    }

    private fun hash(s: CharArray, start: Int): Long {
        var h: Long = 0
        for (i in s.indices) {
            h = h * 131 + s[(start + i) % s.size].code.toLong()
        }
        return h
    }
}