Find the Length of the Longest Common Prefix

Find the Length of the Longest Common Prefix

You are given two arrays with positive integers arr1 and arr2.

A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.

A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have a common prefix 565 while 1223 and 43456 do not have a common prefix.

You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.

LeetCode Problem - 3043

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        // Set to store unique digits present in the elements of arr1.
        Set<Integer> prefix = new HashSet<>();

        // Loop through arr1 elements to extract digits and add them to the set.
        for (int i : arr1){
            while (i > 0){
                prefix.add(i % 10); // Extracting and adding each digit.
                i /= 10; // Move to the next digit.
            }
        }

        int result = 0; // Variable to store the length of the longest common prefix.

        // Loop through arr2 elements to find the common digits.
        for (int i : arr2){
            while (i > 0){
                if (prefix.contains(i)){ // If the digit is present in the set.
                    result = Math.max(result, numLen(i)); // Update the result with maximum length.
                }
                i /= 10; // Move to the next digit.
            }
        }

        return result; // Return the length of the longest common prefix.
    }

    // Function to find the length of a number.
    private int numLen(int num){
        return String.valueOf(num).length(); // Convert the number to a string and return its length.
    }
}

Did you find this article valuable?

Support Gulshan Kumar by becoming a sponsor. Any amount is appreciated!