Flipkart

# 1. Longest Substring of One Repeating Character ## Problem Statement You are given a 0-indexed string `s`. You are also given a 0-indexed string `queryCharacters` of length `k` and a 0-indexed integer array `queryIndices` of length `k`, both of which are used to describe `k` queries. The `i`-th query updates the character in `s` at index `queryIndices[i]` to the character `queryCharacters[i]`. Return an array `lengths` of length `k` where `lengths[i]` is the length of the longest substring of `s` consisting of only one repeating character **after** the `i`-th query is performed. (Hint: This requires maintaining prefix lengths, suffix lengths, and the maximum internal length inside a Segment Tree to handle point updates in logarithmic time.)* ## Constraints `1 <= s.length <= 10^5` `s` consists of lowercase English letters. `k == queryCharacters.length == queryIndices.length` `1 <= k <= 10^5` `queryCharacters` consists of lowercase English letters. `0 <= queryIndices[i] < s.length` ## Test Cases Test Case 1:** *Input:** `s = "babacc"`, `queryCharacters = "bcb"`, `queryIndices = [1,3,3]` *Output:** `[3, 3, 4]` *Explanation:** 1st query updates `s[1]` to 'b'. `s` becomes "b**b**bacc". Longest repeating substring is "bbb" with length 3. 2nd query updates `s[3]` to 'c'. `s` becomes "bbb**c**cc". Longest repeating substring is "bbb" (or "ccc") with length 3. 3rd query updates `s[3]` to 'b'. `s` becomes "bbb**b**cc". Longest repeating substring is "bbbb" with length 4. Test Case 2:** *Input:** `s = "abyzz"`, `queryCharacters = "aa"`, `queryIndices = [2,1]` *Output:** `[2, 3]` *Explanation:** 1st query updates `s[2]` to 'a'. `s` becomes "ab**a**zz". Longest repeating substring is "zz" with length 2. 2nd query updates `s[1]` to 'a'. `s` becomes "a**a**azz". Longest repeating substring is "aaa" with length 3. - # 2. Checking Existence of Edge Length Limited Paths ## Problem Statement An undirected graph of `n` nodes is defined by `edgeList`, where `edgeList[i] = [u_i, v_i, dis_i]` denotes an edge between nodes `u_i` and `v_i` with distance `dis_i`. Note that there may be multiple edges between two nodes. You are given a 2D integer array `queries`, where `queries[j] = [p_j, q_j, limit_j]`. For each query, you must determine whether there is a path between `p_j` and `q_j` such that each edge on the path has a distance **strictly less than** `limit_j`. Return a boolean array `answer`, where `answer.length == queries.length` and `answer[j]` is `true` if there is a path for the `j`-th query, and `false` otherwise. (Hint: Processing the queries completely offline by sorting them and incrementally building components with a Disjoint Set Union (DSU) avoids redundant graph traversals.)* ## Constraints `2 <= n <= 10^5` `1 <= edgeList.length <= 10^5` `edgeList[i].length == 3` `0 <= u_i, v_i < n` `u_i != v_i` `1 <= dis_i <= 10^9` `1 <= queries.length <= 10^5` `queries[j].length == 3` `0 <= p_j, q_j < n` `p_j != q_j` `1 <= limit_j <= 10^9` ## Test Cases Test Case 1:** *Input:** `n = 3`, `edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]]`, `queries = [[0,1,2],[0,2,5]]` *Output:** `[false, true]` *Explanation:** For query 0: The limit is 2. The edge between 0 and 1 has distance 2, which is not strictly less than 2. No path exists. For query 1: The limit is 5. The path [0, 1, 2] uses edges of distances 2 and 4, both strictly less than 5. Path exists. Test Case 2:** *Input:** `n = 5`, `edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]]`, `queries = [[0,4,14],[1,4,13]]` *Output:** `[true, false]` *Explanation:** For query 0: The path [0, 1, 2, 3, 4] has a maximum edge length of 13, which is less than the limit 14. For query 1: To reach node 4 from node 1, the edge [3, 4] with distance 13 must be used. Since this is not strictly less than the limit 13, no valid path exists.