Leetcode QOTD:- 3043. Find the Length of the Longest Common Prefix

Store all prefixes of numbers from arr1 in a HashSet.

Example for 12345:

12345
1234
123
12
1

We get these prefixes by repeatedly dividing by 10.

Then for every number in arr2, keep removing digits from the end and check if that prefix exists in the set.

Example:

1239 → 123 → found

So common prefix length = 3.

break is used because further prefixes (12, 1) will only be smaller.

import java.util.HashSet;

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        HashSet<Integer> prefixes = new HashSet<>();

        // Step 1: Insert all possible prefixes of numbers in arr1 into the HashSet
        for (int val : arr1) {
            while (val > 0) {
                prefixes.add(val);
                val /= 10; // Remove the last digit to get the next prefix
            }
        }

        int maxLength = 0;

        // Step 2: Check all possible prefixes of numbers in arr2 against the HashSet
        for (int val : arr2) {
            while (val > 0) {
                if (prefixes.contains(val)) {
                    // Step 3: If found, calculate its length and update maxLength
                    int currentLength = String.valueOf(val).length();
                    maxLength = Math.max(maxLength, currentLength);

                    // Optimization: Since we are dividing by 10, subsequent prefixes 
                    // of this specific 'val' will be shorter. We can break early.
                    break; 
                }
                val /= 10;
            }
        }

        return maxLength;
    }
}