Skip to content

3485. Longest Common Prefix of K Strings After Removal

SourceBiweekly Contest 152 Q3DifficultyHardRating2289

Description

You are given an array of strings words and an integer k.

For each index i in the range [0, words.length - 1], find the length of the longest common prefix among any k strings (selected at distinct indices) from the remaining array after removing the ith element.

Return an array answer, where answer[i] is the answer for ith element. If removing the ith element leaves the array with fewer than k strings, answer[i] is 0.

 

Example 1:

Input: words = ["jump","run","run","jump","run"], k = 2

Output: [3,4,4,3,4]

Explanation:

  • Removing index 0 ("jump"):
    • words becomes: ["run", "run", "jump", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
  • Removing index 1 ("run"):
    • words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
  • Removing index 2 ("run"):
    • words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
  • Removing index 3 ("jump"):
    • words becomes: ["jump", "run", "run", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
  • Removing index 4 ("run"):
    • words becomes: ["jump", "run", "run", "jump"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).

Example 2:

Input: words = ["dog","racer","car"], k = 2

Output: [0,0,0]

Explanation:

  • Removing any index results in an answer of 0.

 

Constraints:

  • 1 <= k <= words.length <= 105
  • 1 <= words[i].length <= 104
  • words[i] consists of lowercase English letters.
  • The sum of words[i].length is smaller than or equal 105.

Solutions

Solution 1

Thinking

For each deleted word we want the LCP of any \(k\) remaining strings. The total length is \(\le 10^5\), so each query cannot rebuild the trie.

The maximum depth of a trie node with count \(\ge k\) is the global answer. Deleting a word only hurts ancestors whose count is exactly \(k\).

A segment tree keyed by depth stores how many nodes still have count \(\ge k\). We decrement the fragile depths of the deleted word, query the max surviving depth, and roll back. If \(n-1<k\), every answer is \(0\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution:
    def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
        n = len(words)
        ans = [0] * n
        if n - 1 < k:
            return ans

        trie = [{'count': 0, 'depth': 0, 'children': [-1] * 26}]
        for word in words:
            cur = 0
            for c in word:
                idx = ord(c) - 97
                if trie[cur]['children'][idx] == -1:
                    trie[cur]['children'][idx] = len(trie)
                    trie.append(
                        {
                            'count': 0,
                            'depth': trie[cur]['depth'] + 1,
                            'children': [-1] * 26,
                        }
                    )
                cur = trie[cur]['children'][idx]
                trie[cur]['count'] += 1

        max_depth = 0
        for i in range(1, len(trie)):
            if trie[i]['count'] >= k:
                max_depth = max(max_depth, trie[i]['depth'])

        global_count = [0] * (max_depth + 1)
        for i in range(1, len(trie)):
            node = trie[i]
            if node['count'] >= k and node['depth'] <= max_depth:
                global_count[node['depth']] += 1

        fragile_list = [[] for _ in range(n)]
        for i, word in enumerate(words):
            cur = 0
            for c in word:
                idx = ord(c) - 97
                cur = trie[cur]['children'][idx]
                if trie[cur]['count'] == k:
                    fragile_list[i].append(trie[cur]['depth'])

        seg_size = max_depth
        if seg_size < 1:
            return ans

        tree = [-1] * (4 * (seg_size + 1))

        def build(idx: int, l: int, r: int) -> None:
            if l == r:
                tree[idx] = l if global_count[l] > 0 else -1
                return
            mid = (l + r) // 2
            build(idx * 2, l, mid)
            build(idx * 2 + 1, mid + 1, r)
            tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1])

        def update(idx: int, l: int, r: int, pos: int, new_val: int) -> None:
            if l == r:
                tree[idx] = l if new_val > 0 else -1
                return
            mid = (l + r) // 2
            if pos <= mid:
                update(idx * 2, l, mid, pos, new_val)
            else:
                update(idx * 2 + 1, mid + 1, r, pos, new_val)
            tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1])

        build(1, 1, seg_size)
        for i in range(n):
            for d in fragile_list[i]:
                update(1, 1, seg_size, d, global_count[d] - 1)
            res = tree[1]
            ans[i] = 0 if res == -1 else res
            for d in fragile_list[i]:
                update(1, 1, seg_size, d, global_count[d])
        return ans

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Solution {
    static class TrieNode {
        int count = 0;
        int depth = 0;
        int[] children = new int[26];

        TrieNode() {
            for (int i = 0; i < 26; ++i) children[i] = -1;
        }
    }

    static class SegmentTree {
        int n;
        int[] tree;
        int[] globalCount;

        SegmentTree(int n, int[] globalCount) {
            this.n = n;
            this.globalCount = globalCount;
            this.tree = new int[4 * (n + 1)];
            for (int i = 0; i < tree.length; i++) tree[i] = -1;
            build(1, 1, n);
        }

        void build(int idx, int l, int r) {
            if (l == r) {
                tree[idx] = globalCount[l] > 0 ? l : -1;
                return;
            }
            int mid = (l + r) / 2;
            build(idx * 2, l, mid);
            build(idx * 2 + 1, mid + 1, r);
            tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
        }

        void update(int idx, int l, int r, int pos, int newVal) {
            if (l == r) {
                tree[idx] = newVal > 0 ? l : -1;
                return;
            }
            int mid = (l + r) / 2;
            if (pos <= mid) {
                update(idx * 2, l, mid, pos, newVal);
            } else {
                update(idx * 2 + 1, mid + 1, r, pos, newVal);
            }
            tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
        }

        int query() {
            return tree[1];
        }
    }

    public int[] longestCommonPrefix(String[] words, int k) {
        int n = words.length;
        int[] ans = new int[n];
        if (n - 1 < k) return ans;

        ArrayList<TrieNode> trie = new ArrayList<>();
        trie.add(new TrieNode());

        for (String word : words) {
            int cur = 0;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (trie.get(cur).children[idx] == -1) {
                    trie.get(cur).children[idx] = trie.size();
                    TrieNode node = new TrieNode();
                    node.depth = trie.get(cur).depth + 1;
                    trie.add(node);
                }
                cur = trie.get(cur).children[idx];
                trie.get(cur).count++;
            }
        }

        int maxDepth = 0;
        for (int i = 1; i < trie.size(); ++i) {
            if (trie.get(i).count >= k) {
                maxDepth = Math.max(maxDepth, trie.get(i).depth);
            }
        }

        int[] globalCount = new int[maxDepth + 1];
        for (int i = 1; i < trie.size(); ++i) {
            TrieNode node = trie.get(i);
            if (node.count >= k && node.depth <= maxDepth) {
                globalCount[node.depth]++;
            }
        }

        List<List<Integer>> fragileList = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            fragileList.add(new ArrayList<>());
        }

        for (int i = 0; i < n; ++i) {
            int cur = 0;
            for (char c : words[i].toCharArray()) {
                int idx = c - 'a';
                cur = trie.get(cur).children[idx];
                if (trie.get(cur).count == k) {
                    fragileList.get(i).add(trie.get(cur).depth);
                }
            }
        }

        int segSize = maxDepth;
        if (segSize >= 1) {
            SegmentTree segTree = new SegmentTree(segSize, globalCount);
            for (int i = 0; i < n; ++i) {
                if (n - 1 < k) {
                    ans[i] = 0;
                } else {
                    for (int d : fragileList.get(i)) {
                        segTree.update(1, 1, segSize, d, globalCount[d] - 1);
                    }
                    int res = segTree.query();
                    ans[i] = res == -1 ? 0 : res;
                    for (int d : fragileList.get(i)) {
                        segTree.update(1, 1, segSize, d, globalCount[d]);
                    }
                }
            }
        }

        return ans;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
class Solution {
public:
    struct TrieNode {
        int count = 0;
        int depth = 0;
        int children[26] = {0};
    };

    class SegmentTree {
    public:
        int n;
        vector<int> tree;
        vector<int>& globalCount;
        SegmentTree(int n, vector<int>& globalCount)

            : n(n)

            , globalCount(globalCount) {

            tree.assign(4 * (n + 1), -1);
            build(1, 1, n);
        }
        void build(int idx, int l, int r) {
            if (l == r) {
                tree[idx] = globalCount[l] > 0 ? l : -1;
                return;
            }
            int mid = (l + r) / 2;
            build(idx * 2, l, mid);
            build(idx * 2 + 1, mid + 1, r);
            tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
        }
        void update(int idx, int l, int r, int pos, int newVal) {
            if (l == r) {
                tree[idx] = newVal > 0 ? l : -1;
                return;
            }
            int mid = (l + r) / 2;
            if (pos <= mid)
                update(idx * 2, l, mid, pos, newVal);
            else
                update(idx * 2 + 1, mid + 1, r, pos, newVal);
            tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
        }
        int query() {
            return tree[1];
        }
    };

    vector<int> longestCommonPrefix(vector<string>& words, int k) {
        int n = words.size();
        vector<int> ans(n, 0);
        if (n - 1 < k) return ans;
        vector<TrieNode> trie(1);
        for (const string& word : words) {
            int cur = 0;
            for (char c : word) {
                int idx = c - 'a';
                if (trie[cur].children[idx] == 0) {
                    trie[cur].children[idx] = trie.size();
                    trie.push_back({0, trie[cur].depth + 1});
                }
                cur = trie[cur].children[idx];
                trie[cur].count++;
            }
        }
        int maxDepth = 0;
        for (int i = 1; i < trie.size(); ++i) {
            if (trie[i].count >= k) {
                maxDepth = max(maxDepth, trie[i].depth);
            }
        }
        vector<int> globalCount(maxDepth + 1, 0);
        for (int i = 1; i < trie.size(); ++i) {
            if (trie[i].count >= k && trie[i].depth <= maxDepth) {
                globalCount[trie[i].depth]++;
            }
        }
        vector<vector<int>> fragileList(n);
        for (int i = 0; i < n; ++i) {
            int cur = 0;
            for (char c : words[i]) {
                int idx = c - 'a';
                cur = trie[cur].children[idx];
                if (trie[cur].count == k) {
                    fragileList[i].push_back(trie[cur].depth);
                }
            }
        }
        int segSize = maxDepth;
        if (segSize >= 1) {
            SegmentTree segTree(segSize, globalCount);
            for (int i = 0; i < n; ++i) {
                if (n - 1 < k) {
                    ans[i] = 0;
                } else {
                    for (int d : fragileList[i]) {
                        segTree.update(1, 1, segSize, d, globalCount[d] - 1);
                    }
                    int res = segTree.query();
                    ans[i] = res == -1 ? 0 : res;
                    for (int d : fragileList[i]) {
                        segTree.update(1, 1, segSize, d, globalCount[d]);
                    }
                }
            }
        }
        return ans;
    }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
type trieNode struct {
    count    int
    depth    int
    children [26]int
}

func longestCommonPrefix(words []string, k int) []int {
    n := len(words)
    ans := make([]int, n)
    if n-1 < k {
        return ans
    }

    trie := []trieNode{{}}
    for i := range trie[0].children {
        trie[0].children[i] = -1
    }
    for _, word := range words {
        cur := 0
        for _, c := range word {
            idx := int(c - 'a')
            if trie[cur].children[idx] == -1 {
                trie[cur].children[idx] = len(trie)
                node := trieNode{depth: trie[cur].depth + 1}
                for j := range node.children {
                    node.children[j] = -1
                }
                trie = append(trie, node)
            }
            cur = trie[cur].children[idx]
            trie[cur].count++
        }
    }

    maxDepth := 0
    for i := 1; i < len(trie); i++ {
        if trie[i].count >= k {
            maxDepth = max(maxDepth, trie[i].depth)
        }
    }

    globalCount := make([]int, maxDepth+1)
    for i := 1; i < len(trie); i++ {
        if trie[i].count >= k && trie[i].depth <= maxDepth {
            globalCount[trie[i].depth]++
        }
    }

    fragileList := make([][]int, n)
    for i, word := range words {
        cur := 0
        for _, c := range word {
            idx := int(c - 'a')
            cur = trie[cur].children[idx]
            if trie[cur].count == k {
                fragileList[i] = append(fragileList[i], trie[cur].depth)
            }
        }
    }

    segSize := maxDepth
    if segSize < 1 {
        return ans
    }

    tree := make([]int, 4*(segSize+1))
    for i := range tree {
        tree[i] = -1
    }

    var build func(idx, l, r int)
    build = func(idx, l, r int) {
        if l == r {
            if globalCount[l] > 0 {
                tree[idx] = l
            } else {
                tree[idx] = -1
            }
            return
        }
        mid := (l + r) / 2
        build(idx*2, l, mid)
        build(idx*2+1, mid+1, r)
        tree[idx] = max(tree[idx*2], tree[idx*2+1])
    }

    var update func(idx, l, r, pos, newVal int)
    update = func(idx, l, r, pos, newVal int) {
        if l == r {
            if newVal > 0 {
                tree[idx] = l
            } else {
                tree[idx] = -1
            }
            return
        }
        mid := (l + r) / 2
        if pos <= mid {
            update(idx*2, l, mid, pos, newVal)
        } else {
            update(idx*2+1, mid+1, r, pos, newVal)
        }
        tree[idx] = max(tree[idx*2], tree[idx*2+1])
    }

    build(1, 1, segSize)
    for i := 0; i < n; i++ {
        for _, d := range fragileList[i] {
            update(1, 1, segSize, d, globalCount[d]-1)
        }
        res := tree[1]
        if res == -1 {
            ans[i] = 0
        } else {
            ans[i] = res
        }
        for _, d := range fragileList[i] {
            update(1, 1, segSize, d, globalCount[d])
        }
    }
    return ans
}

Comments