Question

How to find the longest shared prefix among all words in a string with Kotlin

Answer 1

import kotlin.text.Regex

// Extract alphabetic words (lowercased)
fun extractWords(text: String): List<String> {
    val regex = Regex("[A-Za-z]+")
    return regex.findAll(text)
        .map { it.value.lowercase() }
        .toList()
}

// Build prefix → list of words that share that prefix
fun groupByPrefixes(words: List<String>): Map<String, List<String>> {
    val groups = mutableMapOf<String, MutableList<String>>()

    for (w in words) {
        for (i in 1..w.length) {
            val prefix = w.substring(0, i)
            groups.computeIfAbsent(prefix) { mutableListOf() }.add(w)
        }
    }

    return groups
}

// Find the longest prefix that appears in 2+ words
fun longestSharedPrefix(groups: Map<String, List<String>>): String? {
    return groups
        .filter { (_, list) -> list.size >= 2 }
        .keys
        .maxByOrNull { it.length }
}

fun main() {
    val text = """
        The Lowly inhabitants of the lowland were surprised to see
        the lower branches of the trees.
    """.trimIndent()

    val words = extractWords(text)
    val groups = groupByPrefixes(words)
    val prefix = longestSharedPrefix(groups)

    if (prefix != null) {
        val group = groups[prefix]!!
        println("Longest shared prefix:")
        println("$prefix | prefix_len=${prefix.length} | group_count=${group.size} | $group")
    } else {
        println("No shared prefix found.")
    }
}



/*
run:

Longest shared prefix:
lowl | prefix_len=4 | group_count=2 | [lowly, lowland]

*/

 

70+ SQL courses for beginners and professionals