5336. Upfall string

















Given a string s, please reconstruct the string according to the following algorithm:
1. Select the smallest character from s and append it to the result string.
2. Select the smallest character from the remaining s character, which is larger than the last added character, and append it to the result string.
3. Repeat step 2 until you cannot select a character from s.
4. Select the largest character from s and append it to the result string.
5. Select the largest character from the remaining s character, which is smaller than the last added character, and append it to the result string.
6. Repeat step 5 until you cannot select a character from s.
7. Repeat steps 1 through 6 until all characters in S are selected.
In any step, if there is more than one minimum or maximum character, you can select either and add it to the resulting string.

Return the result string after reordering the characters in S.

Example:
Enter: s = ‘aaaabbbbCCcc’
Output: ‘abccbaabccba’
Explanation: After steps 1, 2, and 3 of the first round, the result string is result = ‘ABC ‘; After steps 4, 5, and 6 in the first round, the result string is result = ‘abccba’; The first round is over, and now s = ‘aABbcc’, we go back to step 1 again; After steps 1, 2, and 3 in the second round, the result string is result = ‘abccbaabc’; After step 4, step 5, step 6 in round 2, the result string is result = ‘abccbaabccba’








The solution of this problem mainly involves the following points:

  • JavaScript Map data structure

  • Sort sort: sort sort

The algorithm inserts the current character sequence into the resulting string in an odd or even order.

First, a Map is used to record the number of individual characters in the string.

The problem can be solved by judging the parity of the current number and obtaining different monotonically increasing and decreasing sequences.










Vowels contain the largest string of even order

















Given the string s, return the length of the longest string that satisfies the following conditions: each vowel, i.e. ‘a’, ‘e’, ‘I’, ‘O’, ‘u’, occurs exactly an even number of times in the substring.

Example:
Enter: s = ‘eleetminicoworoep’
Output: 13
Explanation: The oldest string is ‘leetminicowor’, which contains two e, I, o, and zero A, U.








The solution to this problem involves the following points:

  • Pruning algorithm

  • An operation

The first solution: the use of violent enumeration method, constantly verify whether the substring meets the requirements.

However, this method is generally unable to AC, because this problem is solving the largest string, so it can filter out the substring shorter than the current result, so as to achieve the purpose of pruning optimization.

The second solution is trickier because there are five characters (Aeiou) and each character has two states, making a total of 32 states, so you can store states in binary and calculate them by xOR operators.










The longest crossing path in a binary tree

















Given a binary tree with root as the root, the staggered paths in the binary tree are defined as follows:

Select any node in the binary tree and a direction (left or right).
Move to the right child of the current node if the forward direction is right, otherwise move to its left child.
Change direction: left to right or right to left.
Repeat steps 2 and 3 until you can no longer move in the tree.
The length of an interleaved path is defined as: number of nodes accessed -1 (the length of a single node path is 0).

Return the length of the longest interleaved path in the given tree.

Example:

Input: [1, null, 1,1,1, null, null, 1, 1, null, 1, null, null, null, 1, null, 1)
Output: 3
Explanation: The blue node is the longest interleaved path in the tree (right -> left -> right).








This problem is mainly about data structure — binary tree.

The key to solving this problem lies in:

  • During recursive traversal, the status of the current subtree (left or right subtree) must be recorded to ensure that the current path is a valid cross path

  • In the process of recursive traversal, it is necessary to record the length of the current crossing path, so as to obtain the longest length by comparison

The code implemented with the recursive idea is very readable and won’t be repeated here.










The maximum key sum of a binary search subtree

















Given a binary tree with root as the root, return the maximum key sum of any binary search subtree.

Binary search trees are defined as follows:

The key in the left subtree of any node is less than the key of that node.
The key in the right subtree of any node is greater than the key of that node.
The left and right subtrees of any node are binary search trees.

Example:
Input: [1,4,3,2,4,2,5, null, null, null, null, null, null, 4, 6]
Output: 20
Explanation: A subtree with a key value of 3 is the largest binary search tree.








This question examines the characteristics associated with BST.

The routine to solve this problem is similar to that in question 3:

  • Determine whether the current subtree is BST during recursive traversal

  • The sum of the current BST is recorded during recursive traversal

Review the conditions for judging subtrees as BST:

  • The left subtree is BST

  • The right subtree is BST

  • Any node in the left subtree is less than the value of this node

  • Any node in the right subtree is greater than the value of this node

According to the above conditions, whether a subtree is a BST depends on its left and right subtrees, so in the recursive traversal process, the four states of the current subtree need to be returned upward:

  • Whether the current subtree is BST

  • The minimum value of a node in the current subtree

  • The maximum number of nodes in the current subtree

  • The sum of the current subtree










Highlights from the past






  • LeetCode Tour for Front-end Engineers — Night Meow Special (20)

  • The front End Engineer’s LeetCode Journey — Binary Tree Easy

  • The LeetCode Journey for front-end Engineers — Binary Tree

  • JavaScript AC solutions to problems on LeetCode