LeetCode Entry

3043. Find the Length of the Longest Common Prefix

21.05.2026 medium 2026 kotlin rust

Longest prefix of pairs

3043. Find the Length of the Longest Common Prefix medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1366

Problem TLDR

Longest prefix of pairs

Intuition

• hashset: put all prefixes of one array, query all prefixes of the second array
• trie: put all prefixes of one array into trie, check longest path for all prefixes of the second

Approach

• we can use strings or ints

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun longestCommonPrefix(a: IntArray, b: IntArray) = run {
        val s = a.flatMap { "$it".scan("", String::plus) }.toSet()
        b.maxOf { var v = "$it"; while (v !in s) v = v.dropLast(1); v.length }
    }

    pub fn longest_common_prefix(a: Vec<i32>, b: Vec<i32>) -> i32 {
        #[derive(Default)] struct T(HashMap<u8, T>); let mut r = T::default();
        for x in a { x.to_string().bytes().fold(&mut r, |t, c| t.0.entry(c).or_default()); }
        b.iter().map(|x| {
            let mut t = &r;
            x.to_string().bytes().take_while(|c| t.0.get(c).map(|n| t = n).is_some()).count() as _
        }).max().unwrap()
    }