3485. Longest Common Prefix of K Strings After Removal

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 i^th element.

Return an array answer, where answer[i] is the answer for i^th element. If removing the i^th 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 <= 10⁵
1 <= words[i].length <= 10⁴
words[i] consists of lowercase English letters.
The sum of words[i].length is smaller than or equal 10⁵.

Solutions

Solution 1

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;
    }
}

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;
    }
};

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

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
}

3485 - Longest Common Prefix of K Strings After Removal

3485. Longest Common Prefix of K Strings After Removal

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3485. Longest Common Prefix of K Strings After Removal

Description

Solutions

Solution 1

All Problems

All Solutions