LeetCode-in-Java

3598. Longest Common Prefix Between Adjacent Strings After Removals

Medium

You are given an array of strings words. For each index i in the range [0, words.length - 1], perform the following steps:

Return an array answer, where answer[i] is the length of the longest common prefix between the adjacent pairs after removing the element at index i. If no adjacent pairs remain or if none share a common prefix, then answer[i] should be 0.

Example 1:

Input: words = [“jump”,”run”,”run”,”jump”,”run”]

Output: [3,0,0,3,3]

Explanation:

Example 2:

Input: words = [“dog”,”racer”,”car”]

Output: [0,0,0]

Explanation:

Constraints:

Solution

public class Solution {
    private int solve(String a, String b) {
        int len = Math.min(a.length(), b.length());
        int cnt = 0;
        while (cnt < len && a.charAt(cnt) == b.charAt(cnt)) {
            cnt++;
        }
        return cnt;
    }

    public int[] longestCommonPrefix(String[] words) {
        int n = words.length;
        int[] ans = new int[n];
        if (n <= 1) {
            return ans;
        }
        int[] lcp = new int[n - 1];
        for (int i = 0; i + 1 < n; i++) {
            lcp[i] = solve(words[i], words[i + 1]);
        }
        int[] prefmax = new int[n - 1];
        int[] sufmax = new int[n - 1];
        prefmax[0] = lcp[0];
        for (int i = 1; i < n - 1; i++) {
            prefmax[i] = Math.max(prefmax[i - 1], lcp[i]);
        }
        sufmax[n - 2] = lcp[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            sufmax[i] = Math.max(sufmax[i + 1], lcp[i]);
        }
        for (int i = 0; i < n; i++) {
            int best = 0;
            if (i >= 2) {
                best = Math.max(best, prefmax[i - 2]);
            }
            if (i + 1 <= n - 2) {
                best = Math.max(best, sufmax[i + 1]);
            }
            if (i > 0 && i < n - 1) {
                best = Math.max(best, solve(words[i - 1], words[i + 1]));
            }
            ans[i] = best;
        }
        return ans;
    }
}