Huahua’s Tech Road

花花酱 LeetCode 1930. Unique Length-3 Palindromic Subsequences

By zxi on December 30, 2021

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Constraints:

3 <= s.length <= 10⁵
s consists of only lowercase English letters.

Solution: Enumerate first character of a palindrome

For a length 3 palindrome, we just need to enumerate the first character c.
We found the first and last occurrence of c in original string and scan the middle part to see how many unique characters there.

e.g. aabca
Enumerate from a to z, looking for a*a, b*b, …, z*z.
For a*a, aabca, we found first and last a, in between is abc, which has 3 unique letters.
We can use a hastable or a bitset to track unique letters.

Time complexity: O(26*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countPalindromicSubsequence(string s) {

auto count = [&](char c) -> int {

int l = s.find_first_of(c);

int r = s.find_last_of(c);

if (l == string::npos || r == string::npos) return 0;

bitset<26> m;

for (int i = l + 1; i < r; ++i)

m.set(s[i] - 'a');

return m.count();

};

int ans = 0;

for (char c = 'a'; c <= 'z'; ++c)

ans += count(c);

return ans;

}

};

花花酱 LeetCode 1929. Concatenation of Array

By zxi on December 30, 2021

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Example 1:

Input: nums = [1,2,1]
Output: [1,2,1,1,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]

Example 2:

Input: nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]

Constraints:

n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000

Solution: Pre-allocation

Pre-allocate an array of length 2 * n.
ans[i] = nums[i % n]

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> getConcatenation(vector<int>& nums) {

const int n = nums.size();

vector<int> ans(2 * n);

for (int i = 0; i < 2 * n; ++i)

ans[i] = nums[i % n];

return ans;

}

};

花花酱 LeetCode 1926. Nearest Exit from Entrance in Maze

By zxi on December 30, 2021

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrance_row, entrance_col] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

Constraints:

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] is either '.' or '+'.
entrance.length == 2
0 <= entrance_row < m
0 <= entrance_col < n
entrance will always be an empty cell.

Solution: BFS

Use BFS to find the shortest path. We can re-use the board for visited array.

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {

const int m = maze.size();

const int n = maze[0].size();

const vector<int> dirs{0, -1, 0, 1, 0};

queue<pair<int, int>> q;

q.emplace(entrance[1], entrance[0]);

for (int steps = 0; !q.empty(); ++steps) {

for (int s = q.size(); s; --s) {

const auto [x, y] = q.front(); q.pop();

if (x == 0 || x == n - 1 || y == 0 || y == m - 1)

if (x != entrance[1] || y != entrance[0])

return steps;

for (int i = 0; i < 4; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m || maze[ty][tx] != '.') continue;

maze[ty][tx] = '*';

q.emplace(tx, ty);

}

return -1;

}

};

花花酱 LeetCode 1925. Count Square Sum Triples

By zxi on December 30, 2021

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

Constraints:

1 <= n <= 250

Solution: Enumerate a & b

Brute force enumerates a & b & c, which takes O(n³). Just need to enumerate a & b and validate c.

Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countTriples(int n) {

int ans = 0;

for (int a = 1; a <= n; ++a)

for (int b = 1; b <= n; ++b) {

int c = sqrt(a * a + b * b);

if (c <= n && c * c == a * a + b * b) ++ans;

}

return ans;

}

};

花花酱 LeetCode 2117. Abbreviating the Product of a Range

By zxi on December 26, 2021

You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right].

Since the product may be very large, you will abbreviate it following these steps:

Count all trailing zeros in the product and remove them. Let us denote this count as C.
- For example, there are 3 trailing zeros in 1000, and there are 0 trailing zeros in 546.
Denote the remaining number of digits in the product as d. If d > 10, then express the product as <pre>...<suf> where <pre> denotes the first 5 digits of the product, and <suf> denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
- For example, we express 1234567654321 as 12345...54321, but 1234567 is represented as 1234567.
Finally, represent the product as a string "<pre>...<suf>eC".
- For example, 12345678987600000 will be represented as "12345...89876e5".

Return a string denoting the abbreviated product of all integers in the inclusive range [left, right].

Example 1:

Input: left = 1, right = 4
Output: "24e0"
Explanation:
The product is 1 × 2 × 3 × 4 = 24.
There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0".
Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further.
Thus, the final representation is "24e0".

Example 2:

Input: left = 2, right = 11
Output: "399168e2"
Explanation:
The product is 39916800.
There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2".
The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.
Hence, the abbreviated product is "399168e2".

Example 3:

Input: left = 999998, right = 1000000
Output: "99999...00002e6"
Explanation:
The above diagram shows how we abbreviate the product to "99999...00002e6".
- It has 6 trailing zeros. The abbreviation will end with "e6".
- The first 5 digits are 99999.
- The last 5 digits after removing trailing zeros is 00002.

Constraints:

1 <= left <= right <= 10⁶

Solution: Prefix + Suffix

Since we only need the first 5 digits and last 5 digits, we can compute prefix and suffix separately with 15+ effective digits. Note, if using long/int64 with (18 – 6) = 12 effective digits, it may fail on certain test cases. Thus, here we use Python with 18 effective digits.

Time complexity: O(mlog(right)) where m = right – left + 1
Space complexity: O(1)

Python3

# Author: Huahua

class Solution:

def abbreviateProduct(self, left: int, right: int) -> str:

kMax = 10 ** 18

prefix = 1

suffix = 1

c = 0

for i in range(left, right + 1):

prefix *= i

while prefix >= kMax:

prefix //= 10

suffix *= i

while suffix % 10 == 0:

suffix //= 10

c += 1

suffix %= kMax

p, s = str(prefix), str(suffix)

return (s if len(s) <= 10 else p[:5] + "..." + s[-5:]) + "e" + str(c);

Huahua's Tech Road

花花酱 LeetCode 1930. Unique Length-3 Palindromic Subsequences

Solution: Enumerate first character of a palindrome

C++

花花酱 LeetCode 1929. Concatenation of Array

Solution: Pre-allocation

C++

花花酱 LeetCode 1926. Nearest Exit from Entrance in Maze

Solution: BFS

C++

花花酱 LeetCode 1925. Count Square Sum Triples

Solution: Enumerate a & b

C++

花花酱 LeetCode 2117. Abbreviating the Product of a Range

Solution: Prefix + Suffix

Python3