2024-10-14
2530. Maximal Score After Applying K Operations

Topic: Array, Greedy, Heap (Priority Queue)
Difficulty: Medium

Problem:
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

1. choose an index i such that 0 <= i < nums.length,
2. increase your score by nums[i], and
3. replace nums[i] with ceil(nums[i] / 3).

Return the maximum possible score you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

Example 1:

Input: nums = [10,10,10,10,10], k = 5
Output: 50
Explanation: Apply the operation to each array element exactly once. The final score is 10 + 10 + 10 + 10 + 10 = 50.

Example 2:

Input: nums = [1,10,3,3,3], k = 3
Output: 17
Explanation: You can do the following operations:
Operation 1: Select i = 1, so nums becomes [1,4,3,3,3]. Your score increases by 10.
Operation 2: Select i = 1, so nums becomes [1,2,3,3,3]. Your score increases by 4.
Operation 3: Select i = 2, so nums becomes [1,1,1,3,3]. Your score increases by 3.
The final score is 10 + 4 + 3 = 17.

Constraints:

• 1 <= nums.length, k <= 10^5
• 1 <= nums[i] <= 10^9

2024-10-15
2938. Separate Black and White Balls

Topic: Two Pointers, String, Greedy
Difficulty: Medium

Problem:
There are n balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

Example 1:

Input: s = "101"
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Example 2:

Input: s = "100"
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "010".
- Swap s[1] and s[2], s = "001".
It can be proven that the minimum number of steps needed is 2.

Example 3:

Input: s = "0111"
Output: 0
Explanation: All the black balls are already grouped to the right.

Constraints:

• 1 <= n == s.length <= 10^5
• s[i] is either '0' or '1'.

2024-10-16
1405. Longest Happy String

Topic: String, Greedy, Heap (Priority Queue)
Difficulty: Medium

Problem:
A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

2024-10-17
670. Maximum Swap

Topic: Math, Greedy
Difficulty: Medium

Problem:
You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

• 0 <= num <= 10^8

2024-10-18
2044. Count Number of Maximum Bitwise-OR Subsets

Topic: Array, Backtracking, Bit Manipulation, Enumeration
Difficulty: Medium

Problem:
Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 2^3 - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

Constraints:

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 10^5

2024-10-19
1545. Find Kth Bit in Nth Binary String

Topic: String, Recursion, Simulation
Difficulty: Medium

Problem:
Given two positive integers n and k, the binary string S_n is formed as follows:

• S_1 = "0"
• S_i = S_i - 1 + "1" + reverse(invert(S_i - 1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first four strings in the above sequence are:

• S_1 = "0"
• S_2 = "011"
• S_3 = "0111001"
• S_4 = "011100110110001"

Return the k^th bit in S_n. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S_3 is "0111001".
The 1^st bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S_4 is "011100110110001".
The 11^th bit is "1".

Constraints:

• 1 <= n <= 20
• 1 <= k <= 2^n - 1

2024-10-20
1106. Parsing A Boolean Expression

Topic: String, Stack, Recursion
Difficulty: Hard

Problem:
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

• 't' that evaluates to true.
• 'f' that evaluates to false.
• '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
• '&(subExpr_1, subExpr_2, ..., subExpr_n)' that evaluates to the logical AND of the inner expressions subExpr_1, subExpr_2, ..., subExpr_n where n >= 1.
• '|(subExpr_1, subExpr_2, ..., subExpr_n)' that evaluates to the logical OR of the inner expressions subExpr_1, subExpr_2, ..., subExpr_n where n >= 1.

Given a string expression that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Example 1:

Input: expression = "&(|(f))"
Output: false
Explanation: 
First, evaluate |(f) --> f. The expression is now "&(f)".
Then, evaluate &(f) --> f. The expression is now "f".
Finally, return false.

Example 2:

Input: expression = "|(f,f,f,t)"
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3:

Input: expression = "!(&(f,t))"
Output: true
Explanation: 
First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.

Constraints:

• 1 <= expression.length <= 2 * 10^4
• expressioni is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

2024-10-21
1593. Split a String Into the Max Number of Unique Substrings

Topic: Hash Table, String, Backtracking
Difficulty: Medium

Problem:
Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

Constraints:

• 1 <= s.length <= 16
• s contains only lower case English letters.

2024-10-22
2583. Kth Largest Sum in a Binary Tree

Topic: Tree, Breadth-First Search, Sorting, Binary Tree
Difficulty: Medium

Problem:
You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/12/14/binaryytreeedrawio-2.png

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2^nd largest level sum is 13.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/12/14/treedrawio-3.png

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

Constraints:

• The number of nodes in the tree is n.
• 2 <= n <= 10^5
• 1 <= Node.val <= 10^6
• 1 <= k <= n

2024-10-23
2641. Cousins in Binary Tree II

Topic: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins' values.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Return the root of the modified tree.

Note that the depth of a node is the number of edges in the path from the root node to it.

Example 1:

Image: https://assets.leetcode.com/uploads/2023/01/11/example11.png

Input: root = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 5 does not have any cousins so its sum is 0.
- Node with value 4 does not have any cousins so its sum is 0.
- Node with value 9 does not have any cousins so its sum is 0.
- Node with value 1 has a cousin with value 7 so its sum is 7.
- Node with value 10 has a cousin with value 7 so its sum is 7.
- Node with value 7 has cousins with values 1 and 10 so its sum is 11.

Example 2:

Image: https://assets.leetcode.com/uploads/2023/01/11/diagram33.png

Input: root = [3,1,2]
Output: [0,0,0]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 3 does not have any cousins so its sum is 0.
- Node with value 1 does not have any cousins so its sum is 0.
- Node with value 2 does not have any cousins so its sum is 0.

Constraints:

• The number of nodes in the tree is in the range [1, 10^5].
• 1 <= Node.val <= 10^4

2024-10-24
951. Flip Equivalent Binary Trees

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

Problem:
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

Example 1:

Image: https://assets.leetcode.com/uploads/2018/11/29/tree_ex.png

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Example 2:

Input: root1 = [], root2 = []
Output: true

Example 3:

Input: root1 = [], root2 = [1]
Output: false

Constraints:

• The number of nodes in each tree is in the range [0, 100].
• Each tree will have unique node values in the range [0, 99].

2024-10-25
1233. Remove Sub-Folders from the Filesystem

Topic: Array, String, Depth-First Search, Trie
Difficulty: Medium

Problem:
Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

• For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

• 1 <= folder.length <= 4 * 10^4
• 2 <= folder[i].length <= 100
• folder[i] contains only lowercase letters and '/'.
• folder[i] always starts with the character '/'.
• Each folder name is unique.

2024-10-26
2458. Height of Binary Tree After Subtree Removal Queries

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

Problem:
You are given the root of a binary tree with n nodes. Each node is assigned a unique value from 1 to n. You are also given an array queries of size m.

You have to perform m independent queries on the tree where in the i^th query you do the following:

• Remove the subtree rooted at the node with the value queries[i] from the tree. It is guaranteed that queries[i] will not be equal to the value of the root.

Return an array answer of size m where answer[i] is the height of the tree after performing the i^th query.

Note:

• The queries are independent, so the tree returns to its initial state after each query.
• The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png

Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
The height of the tree is 2 (The path 1 -> 3 -> 2).

Example 2:

Image: https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png

Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).

Constraints:

• The number of nodes in the tree is n.
• 2 <= n <= 10^5
• 1 <= Node.val <= n
• All the values in the tree are unique.
• m == queries.length
• 1 <= m <= min(n, 10^4)
• 1 <= queries[i] <= n
• queries[i] != root.val

2024-10-27
1277. Count Square Submatrices with All Ones

Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium

Problem:
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

2024-10-28
2501. Longest Square Streak in an Array

Topic: Array, Hash Table, Binary Search, Dynamic Programming, Sorting
Difficulty: Medium

Problem:
You are given an integer array nums. A subsequence of nums is called a square streak if:

• The length of the subsequence is at least 2, and
• after sorting the subsequence, each element (except the first element) is the square of the previous number.

Return the length of the longest square streak in nums, or return -1 if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,3,6,16,8,2]
Output: 3
Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.

Example 2:

Input: nums = [2,3,5,6,7]
Output: -1
Explanation: There is no square streak in nums so return -1.

Constraints:

• 2 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^5

2024-10-29
2684. Maximum Number of Moves in a Grid

Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium

Problem:
You are given a 0-indexed m x n matrix grid consisting of positive integers.

You can start at any cell in the first column of the matrix, and traverse the grid in the following way:

• From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell.

Return the maximum number of moves that you can perform.

Example 1:

Image: https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png

Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
Output: 3
Explanation: We can start at the cell (0, 0) and make the following moves:
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
It can be shown that it is the maximum number of moves that can be made.

Example 2:

Image: [https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png](https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png)

Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
Output: 0
Explanation: Starting from any cell in the first column we cannot perform any moves.

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^6

2024-10-30
1671. Minimum Number of Removals to Make Mountain Array

Topic: Array, Binary Search, Dynamic Programming, Greedy
Difficulty: Hard

Problem:
You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Constraints:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9
• It is guaranteed that you can make a mountain array out of nums.

2024-10-31
2463. Minimum Total Distance Traveled

Topic: Array, Dynamic Programming, Sorting
Difficulty: Hard

Problem:
There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the i^th robot. You are also given a 2D integer array factory where factory[j] = [position_j, limit_j] indicates that position_j is the position of the j^th factory and that the j^th factory can repair at most limit_j robots.

The positions of each robot are unique. The positions of each factory are also unique. Note that a robot can be in the same position as a factory initially.

All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the positive direction of the X-axis. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving.

At any moment, you can set the initial direction of moving for some robot. Your target is to minimize the total distance traveled by all the robots.

Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.

Note that

• All robots move at the same speed.
• If two robots move in the same direction, they will never collide.
• If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
• If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
• If the robot moved from a position x to a position y, the distance it moved is |y - x|.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/09/15/example1.jpg

Input: robot = [0,4,6], factory = [[2,2],[6,2]]
Output: 4
Explanation: As shown in the figure:
- The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
- The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
- The third robot at position 6 will be repaired at the second factory. It does not need to move.
The limit of the first factory is 2, and it fixed 2 robots.
The limit of the second factory is 2, and it fixed 1 robot.
The total distance is |2 - 0| + |2 - 4| + |6 - 6| = 4. It can be shown that we cannot achieve a better total distance than 4.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/09/15/example-2.jpg

Input: robot = [1,-1], factory = [[-2,1],[2,1]]
Output: 2
Explanation: As shown in the figure:
- The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
- The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
The limit of the first factory is 1, and it fixed 1 robot.
The limit of the second factory is 1, and it fixed 1 robot.
The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.

Constraints:

• 1 <= robot.length, factory.length <= 100
• factory[j].length == 2
• -10^9 <= robot[i], position_j <= 10^9
• 0 <= limit_j <= robot.length
• The input will be generated such that it is always possible to repair every robot.

2024-11-01
1957. Delete Characters to Make Fancy String

Topic: String
Difficulty: Easy

Problem:
A fancy string is a string where no three consecutive characters are equal.

Given a string s, delete the minimum possible number of characters from s to make it fancy.

Return the final string after the deletion. It can be shown that the answer will always be unique.

Example 1:

Input: s = "leeetcode"
Output: "leetcode"
Explanation:
Remove an 'e' from the first group of 'e's to create "leetcode".
No three consecutive characters are equal, so return "leetcode".

Example 2:

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation:
Remove an 'a' from the first group of 'a's to create "aabaaaa".
Remove two 'a's from the second group of 'a's to create "aabaa".
No three consecutive characters are equal, so return "aabaa".

Example 3:

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so return "aab".

Constraints:

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

2024-11-02
2490. Circular Sentence

Topic: String
Difficulty: Easy

Problem:
A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

• For example, "Hello World", "HELLO", "hello world hello world" are all sentences.

Words consist of only uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.

A sentence is circular if:

• The last character of a word is equal to the first character of the next word.
• The last character of the last word is equal to the first character of the first word.

For example, "leetcode exercises sound delightful", "eetcode", "leetcode eats soul" are all circular sentences. However, "Leetcode is cool", "happy Leetcode", "Leetcode" and "I like Leetcode" are not circular sentences.

Given a string sentence, return true if it is circular. Otherwise, return false.

Example 1:

Input: sentence = "leetcode exercises sound delightful"
Output: true
Explanation: The words in sentence are ["leetcode", "exercises", "sound", "delightful"].
- leetcode's last character is equal to exercises's first character.
- exercises's last character is equal to sound's first character.
- sound's last character is equal to delightful's first character.
- delightful's last character is equal to leetcode's first character.
The sentence is circular.

Example 2:

Input: sentence = "eetcode"
Output: true
Explanation: The words in sentence are ["eetcode"].
- eetcode's last character is equal to eetcode's first character.
The sentence is circular.

Example 3:

Input: sentence = "Leetcode is cool"
Output: false
Explanation: The words in sentence are ["Leetcode", "is", "cool"].
- Leetcode's last character is not equal to is's first character.
The sentence is not circular.

Constraints:

• 1 <= sentence.length <= 500
• sentence consist of only lowercase and uppercase English letters and spaces.
• The words in sentence are separated by a single space.
• There are no leading or trailing spaces.