2025-05-23
3068. Find the Maximum Sum of Node Values

Topic: Array, Dynamic Programming, Greedy, Bit Manipulation, Tree, Sorting
Difficulty: Hard

Problem:
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the tree. You are also given a positive integer k, and a 0-indexed array of non-negative integers nums of length n, where nums[i] represents the value of the node numbered i.

Alice wants the sum of values of tree nodes to be maximum, for which Alice can perform the following operation any number of times (including zero) on the tree:

• Choose any edge [u, v] connecting the nodes u and v, and update their values as follows:
• nums[u] = nums[u] XOR k
• nums[v] = nums[v] XOR k

Return the maximum possible sum of the values Alice can achieve by performing the operation any number of times.

Example 1:

Image: https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png

Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
Output: 6
Explanation: Alice can achieve the maximum sum of 6 using a single operation:
- Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2].
The total sum of values is 2 + 2 + 2 = 6.
It can be shown that 6 is the maximum achievable sum of values.

Example 2:

Image: https://assets.leetcode.com/uploads/2024/01/09/screenshot-2024-01-09-220017.png

Input: nums = [2,3], k = 7, edges = [[0,1]]
Output: 9
Explanation: Alice can achieve the maximum sum of 9 using a single operation:
- Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4].
The total sum of values is 5 + 4 = 9.
It can be shown that 9 is the maximum achievable sum of values.

Example 3:

Image: https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png

Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
Output: 42
Explanation: The maximum achievable sum is 42 which can be achieved by Alice performing no operations.

Constraints:

• 2 <= n == nums.length <= 2 * 10^4
• 1 <= k <= 10^9
• 0 <= nums[i] <= 10^9
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• The input is generated such that edges represent a valid tree.

2025-05-24
2942. Find Words Containing Character

Topic: Array, String
Difficulty: Easy

Problem:
You are given a 0-indexed array of strings words and a character x.

Return an array of indices representing the words that contain the character x.

Note that the returned array may be in any order.

Example 1:

Input: words = ["leet","code"], x = "e"
Output: [0,1]
Explanation: "e" occurs in both words: "leet", and "code". Hence, we return indices 0 and 1.

Example 2:

Input: words = ["abc","bcd","aaaa","cbc"], x = "a"
Output: [0,2]
Explanation: "a" occurs in "abc", and "aaaa". Hence, we return indices 0 and 2.

Example 3:

Input: words = ["abc","bcd","aaaa","cbc"], x = "z"
Output: []
Explanation: "z" does not occur in any of the words. Hence, we return an empty array.

Constraints:

• 1 <= words.length <= 50
• 1 <= words[i].length <= 50
• x is a lowercase English letter.
• words[i] consists only of lowercase English letters.

2025-05-25
2131. Longest Palindrome by Concatenating Two Letter Words

Topic: Array, Hash Table, String, Greedy, Counting
Difficulty: Medium

Problem:
You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

• 1 <= words.length <= 10^5
• words[i].length == 2
• words[i] consists of lowercase English letters.

2025-05-26
1857. Largest Color Value in a Directed Graph

Topic: Hash Table, Dynamic Programming, Graph, Topological Sort, Memoization, Counting
Difficulty: Hard

Problem:
There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x_1 -> x_2 -> x_3 -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/04/21/leet1.png

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

Image: https://assets.leetcode.com/uploads/2021/04/21/leet2.png

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints:

• n == colors.length
• m == edges.length
• 1 <= n <= 10^5
• 0 <= m <= 10^5
• colors consists of lowercase English letters.
• 0 <= a_j, b_j < n

2025-05-27
2894. Divisible and Non-divisible Sums Difference

Topic: Math
Difficulty: Easy

Problem:
You are given positive integers n and m.

Define two integers as follows:

• num1: The sum of all integers in the range [1, n] (both inclusive) that are not divisible by m.
• num2: The sum of all integers in the range [1, n] (both inclusive) that are divisible by m.

Return the integer num1 - num2.

Example 1:

Input: n = 10, m = 3
Output: 19
Explanation: In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.

Example 2:

Input: n = 5, m = 6
Output: 15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.

Example 3:

Input: n = 5, m = 1
Output: -15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.

Constraints:

• 1 <= n, m <= 1000

2025-05-28
3372. Maximize the Number of Target Nodes After Connecting Trees I

Topic: Tree, Depth-First Search, Breadth-First Search
Difficulty: Medium

Problem:
There exist two undirected trees with n and m nodes, with distinct labels in ranges [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree. You are also given an integer k.

Node u is target to node v if the number of edges on the path from u to v is less than or equal to k. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes target to node i of the first tree if you have to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Example 1:

Input: edges1 = [0,1,0,2,2,3,2,4], edges2 = [0,1,0,2,0,3,2,7,1,4,4,5,4,6], k = 2

Output: 9,7,9,8,8

Explanation:

• For i = 0, connect node 0 from the first tree to node 0 from the second tree.
• For i = 1, connect node 1 from the first tree to node 0 from the second tree.
• For i = 2, connect node 2 from the first tree to node 4 from the second tree.
• For i = 3, connect node 3 from the first tree to node 4 from the second tree.
• For i = 4, connect node 4 from the first tree to node 4 from the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3982-1.png

Example 2:

Input: edges1 = [0,1,0,2,0,3,0,4], edges2 = [0,1,1,2,2,3], k = 1

Output: 6,3,3,3,3

Explanation:

For every i, connect node i of the first tree with any node of the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3928-2.png

Constraints:

• 2 <= n, m <= 1000
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• The input is generated such that edges1 and edges2 represent valid trees.
• 0 <= k <= 1000

2025-05-29
3373. Maximize the Number of Target Nodes After Connecting Trees II

Topic: Tree, Depth-First Search, Breadth-First Search
Difficulty: Hard

Problem:
There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree.

Node u is target to node v if the number of edges on the path from u to v is even. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes that are target to node i of the first tree if you had to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Example 1:

Input: edges1 = [0,1,0,2,2,3,2,4], edges2 = [0,1,0,2,0,3,2,7,1,4,4,5,4,6]

Output: 8,7,7,8,8

Explanation:

• For i = 0, connect node 0 from the first tree to node 0 from the second tree.
• For i = 1, connect node 1 from the first tree to node 4 from the second tree.
• For i = 2, connect node 2 from the first tree to node 7 from the second tree.
• For i = 3, connect node 3 from the first tree to node 0 from the second tree.
• For i = 4, connect node 4 from the first tree to node 4 from the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3982-1.png

Example 2:

Input: edges1 = [0,1,0,2,0,3,0,4], edges2 = [0,1,1,2,2,3]

Output: 3,6,6,6,6

Explanation:

For every i, connect node i of the first tree with any node of the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3928-2.png

Constraints:

• 2 <= n, m <= 10^5
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• The input is generated such that edges1 and edges2 represent valid trees.

2025-05-30
2359. Find Closest Node to Given Two Nodes

Topic: Depth-First Search, Graph
Difficulty: Medium

Problem:
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from i, then edges[i] == -1.

You are also given two integers node1 and node2.

Return the index of the node that can be reached from both node1 and node2, such that the maximum between the distance from node1 to that node, and from node2 to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.

Note that edges may contain cycles.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-2.png

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-4.png

Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.

Constraints:

• n == edges.length
• 2 <= n <= 10^5
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

2025-05-31
909. Snakes and Ladders

Topic: Array, Breadth-First Search, Matrix
Difficulty: Medium

Problem:
You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

• Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n^2)].
• This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
• If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
• The game ends when you reach the square n^2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n^2 are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per dice roll. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

• For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of dice rolls required to reach the square n^2. If it is not possible to reach the square, return -1.

Example 1:

Image: https://assets.leetcode.com/uploads/2018/09/23/snakes.png

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

Constraints:

• n == board.length == board[i].length
• 2 <= n <= 20
• board[i][j] is either -1 or in the range [1, n^2].
• The squares labeled 1 and n^2 are not the starting points of any snake or ladder.

2025-06-01
2929. Distribute Candies Among Children II

Topic: Math, Combinatorics, Enumeration
Difficulty: Medium

Problem:
You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

Constraints:

• 1 <= n <= 10^6
• 1 <= limit <= 10^6

2025-06-02
135. Candy

Topic: Array, Greedy
Difficulty: Hard

Problem:
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

2025-06-03
1298. Maximum Candies You Can Get from Boxes

Topic: Array, Breadth-First Search, Graph
Difficulty: Hard

Problem:
You have n boxes labeled from 0 to n - 1. You are given four arrays: status, candies, keys, and containedBoxes where:

• status[i] is 1 if the i^th box is open and 0 if the i^th box is closed,
• candies[i] is the number of candies in the i^th box,
• keys[i] is a list of the labels of the boxes you can open after opening the i^th box.
• containedBoxes[i] is a list of the boxes you found inside the i^th box.

You are given an integer array initialBoxes that contains the labels of the boxes you initially have. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2.
Box 1 is closed and you do not have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:

Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys.
The total number of candies will be 6.

Constraints:

• n == status.length == candies.length == keys.length == containedBoxes.length
• 1 <= n <= 1000
• status[i] is either 0 or 1.
• 1 <= candies[i] <= 1000
• 0 <= keys[i].length <= n
• 0 <= keys[i][j] < n
• All values of keys[i] are unique.
• 0 <= containedBoxes[i].length <= n
• 0 <= containedBoxes[i][j] < n
• All values of containedBoxes[i] are unique.
• Each box is contained in one box at most.
• 0 <= initialBoxes.length <= n
• 0 <= initialBoxes[i] < n

2025-06-04
3403. Find the Lexicographically Largest String From the Box I

Topic: Two Pointers, String, Enumeration
Difficulty: Medium

Problem:
You are given a string word, and an integer numFriends.

Alice is organizing a game for her numFriends friends. There are multiple rounds in the game, where in each round:

• word is split into numFriends non-empty strings, such that no previous round has had the exact same split.
• All the split words are put into a box.

Find the lexicographically largest string from the box after all the rounds are finished.

Example 1:

Input: word = "dbca", numFriends = 2

Output: "dbc"

Explanation: 

All possible splits are:

• "d" and "bca".
• "db" and "ca".
• "dbc" and "a".

Example 2:

Input: word = "gggg", numFriends = 4

Output: "g"

Explanation: 

The only possible split is: "g", "g", "g", and "g".

Constraints:

• 1 <= word.length <= 5 * 10^3
• word consists only of lowercase English letters.
• 1 <= numFriends <= word.length

2025-06-05
1061. Lexicographically Smallest Equivalent String

Topic: String, Union Find
Difficulty: Medium

Problem:
You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

• For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'.
• Symmetry: 'a' == 'b' implies 'b' == 'a'.
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Example 1:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

Example 2:

Input: s1 = "hello", s2 = "world", baseStr = "hold"
Output: "hdld"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r].
So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

Example 3:

Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
Output: "aauaaaaada"
Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

Constraints:

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

2025-06-06
2434. Using a Robot to Print the Lexicographically Smallest String

Topic: Hash Table, String, Stack, Greedy
Difficulty: Medium

Problem:
You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

• Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
• Remove the last character of a string t and give it to the robot. The robot will write this character on paper.

Return the lexicographically smallest string that can be written on the paper.

Example 1:

Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".

Example 2:

Input: s = "bac"
Output: "abc"
Explanation: Let p denote the written string.
Perform first operation twice p="", s="c", t="ba". 
Perform second operation twice p="ab", s="c", t="". 
Perform first operation p="ab", s="", t="c". 
Perform second operation p="abc", s="", t="".

Example 3:

Input: s = "bdda"
Output: "addb"
Explanation: Let p denote the written string.
Initially p="", s="bdda", t="".
Perform first operation four times p="", s="", t="bdda".
Perform second operation four times p="addb", s="", t="".

Constraints:

• 1 <= s.length <= 10^5
• s consists of only English lowercase letters.

2025-06-08
386. Lexicographical Numbers

Topic: Depth-First Search, Trie
Difficulty: Medium

Problem:
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2]

Constraints:

• 1 <= n <= 5 * 10^4

2025-06-09
440. K-th Smallest in Lexicographical Order

Topic: Trie
Difficulty: Hard

Problem:
Given two integers n and k, return the k^th lexicographically smallest integer in the range [1, n].

Example 1:

Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:

Input: n = 1, k = 1
Output: 1

Constraints:

• 1 <= k <= n <= 10^9

2025-06-10
3442. Maximum Difference Between Even and Odd Frequency I

Topic: Hash Table, String, Counting
Difficulty: Easy

Problem:
You are given a string s consisting of lowercase English letters.

Your task is to find the maximum difference diff = a_1 - a_2 between the frequency of characters a_1 and a_2 in the string such that:

• a_1 has an odd frequency in the string.
• a_2 has an even frequency in the string.

Return this maximum difference.

Example 1:

Input: s = "aaaaabbc"

Output: 3

Explanation:

• The character 'a' has an odd frequency of 5, and 'b' has an even frequency of 2.
• The maximum difference is 5 - 2 = 3.

Example 2:

Input: s = "abcabcab"

Output: 1

Explanation:

• The character 'a' has an odd frequency of 3, and 'c' has an even frequency of 2.
• The maximum difference is 3 - 2 = 1.

Constraints:

• 3 <= s.length <= 100
• s consists only of lowercase English letters.
• s contains at least one character with an odd frequency and one with an even frequency.

2025-06-11
3445. Maximum Difference Between Even and Odd Frequency II

Topic: String, Sliding Window, Enumeration, Prefix Sum
Difficulty: Hard

Problem:
You are given a string s and an integer k. Your task is to find the maximum difference between the frequency of two characters, freq[a] - freq[b], in a substring subs of s, such that:

• subs has a size of at least k.
• Character a has an odd frequency in subs.
• Character b has an even frequency in subs.

Return the maximum difference.

Note that subs can contain more than 2 distinct characters.

Example 1:

Input: s = "12233", k = 4

Output: -1

Explanation:

For the substring "12233", the frequency of '1' is 1 and the frequency of '3' is 2. The difference is 1 - 2 = -1.

Example 2:

Input: s = "1122211", k = 3

Output: 1

Explanation:

For the substring "11222", the frequency of '2' is 3 and the frequency of '1' is 2. The difference is 3 - 2 = 1.

Example 3:

Input: s = "110", k = 3

Output: -1

Constraints:

• 3 <= s.length <= 3 * 10^4
• s consists only of digits '0' to '4'.
• The input is generated that at least one substring has a character with an even frequency and a character with an odd frequency.
• 1 <= k <= s.length

2025-06-12
3423. Maximum Difference Between Adjacent Elements in a Circular Array

Topic: Array
Difficulty: Easy

Problem:
Given a circular array nums, find the maximum absolute difference between adjacent elements.

Note: In a circular array, the first and last elements are adjacent.

Example 1:

Input: nums = 1,2,4

Output: 3

Explanation:

Because nums is circular, nums[0] and nums[2] are adjacent. They have the maximum absolute difference of |4 - 1| = 3.

Example 2:

Input: nums = -5,-10,-5

Output: 5

Explanation:

The adjacent elements nums[0] and nums[1] have the maximum absolute difference of |-5 - (-10)| = 5.

Constraints:

• 2 <= nums.length <= 100
• -100 <= nums[i] <= 100