作为一个在算法题海里卷生卷死的“过来人”，每次刷到那种看起来很简单但实际一不小心就“错失满分”的题目，我都忍不住想高呼一句：“细节才是王道！”🔥

这篇笔记就是要跟大家分享两道近期超高频出现、但很多人依然会踩坑的笔试题：一道是关于字符串字典序优化的小技巧题，另一道是考验你是否真正掌握位运算+动态规划组合技的序列题。两道题的共通点？乍一看像送分题，但真正想拿高分，你得又快又准下手！

📌看完这篇，不光能掌握思路，还有贴心的“最优选择逻辑”分析，让你面试时直接Copy Paste脑回路，刷题路上不再迷路～

1. Smallest String

Given a string s that consists of lowercase English letters, select exactly one non-empty substring of s and replace each character of it with the previous character of the English alphabet. For example, 'b' is converted to 'a', 'c' is converted to 'b', ..., and 'a' is converted to 'z'.

Find the alphabetically smallest string that can be obtained after performing the above operation exactly once.

Example

s = "hackerrank"

Select    New string
h         gackerrank
ha        gzckerrank
err       hackdqqank

Select and change only the first character. Return "gackerrank", the alphabetically smallest string possible.

Function Description

Complete the function getSmallestString in the editor below.

getSmallestString has the following parameter:

• s: a string

Return

• string: the alphabetically smallest string possible

Constraints

• 1 ≤ length of s, |s| ≤ 10⁵

Sample Case 0

Sample Input For Custom Testing

STDIN       FUNCTION
----------- ---------------------
"bbcad"     string s = "bbcad"

Sample Output

aabad

Explanation

Change bbc to aab.

2. Bitwise XOR Subsequences

A subsequence of an array is formed by removing zero or more elements from an array without changing the order of the remaining elements. In a valid subsequence, each pair of adjacent elements of the subsequence has bitwise XOR equal to k. Note that any subsequence of length 1 is valid regardless of the value of k, because there is no pair of adjacent elements in such a subsequence.

Given an array of integers and integer k, determine the length of the longest valid subsequence in the array.

Example

n = 5
arr = [2, 1, 3, 5, 2]
k = 2

The subsequence [1, 3] is valid because for all pairs of adjacent elements it has (1 and 3), the bitwise XOR of such elements is equal to k (1 XOR 3 = 2). There are no other valid subsequences that are longer than 2. For example, subsequence [2, 1, 3] is not valid because 2 XOR 1 does not equal 2.

Function Description

Complete the function maxSubsequenceLength in the editor below. The function must return the length of the longest valid subsequence of the array, given parameter k.

maxSubsequenceLength has the following parameters:

• int n: the size of arr
• int arr[n]: an array of integers
• int k: an integer

Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ arr[i] ≤ 10⁶
• 0 ≤ k ≤ 10⁶

Sample Case 0

Sample Input For Custom Testing

STDIN        Function
-----------  ----------------------------
3            n = 3
0            k = 0
3            arr[] size n = 3
1 1 1        arr = [1, 1, 1]

Sample Output

3

Explanation

The longest valid subsequence is the whole array because every pair of adjacent elements is (1, 1) and 1 XOR 1 = 0.

Sample Case 1

Sample Input For Custom Testing

STDIN        Function
-----------  ----------------------------
5            n = 5
5            k = 5
5            arr[] size n = 5
1 2 2 1 3    arr = [1, 2, 2, 1, 3]

Sample Output

3

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.