String – Huahua’s Tech Road

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

By zxi on April 16, 2025

这题考查的是排序吧… 还有rbegin的使用。

普通排序：时间 O(nlogn) / 空间 O(1)

前半部分顺序排序，后半部分逆序排序。

class Solution {

public:

string smallestPalindrome(string s) {

const int n = s.length();

sort(begin(s), begin(s) + n / 2);

sort(rbegin(s), rbegin(s) + n / 2);

return s;

}

};

计数排序：时间：O(n)，空间：O(n) -> O(1)

首尾一起写

// 7 ms, 54.65MB

class Solution {

public:

string smallestPalindrome(string s) {

vector<int> f(128);

for (size_t i = 0; i < s.size() / 2; ++i)

++f[s[i]];

auto h=begin(s);

auto t=rbegin(s);

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

while (f[c]--)

*h++ = *t++ = c;

return s;

}

};

花花酱 LeetCode 2023. Number of Pairs of Strings With Concatenation Equal to Target

By zxi on April 11, 2025

方法1: Brute Force

枚举所有的(nums[i], nums[j])组合，相加在和target比较。

时间复杂度：O(mn²) m为字符串的最长长度。
空间复杂度：O(m)

优化前 67ms, 49.3M

class Solution {

public:

int numOfPairs(vector<string>& nums, string target) {

const int n = nums.size();

int ans = 0;

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

for (int j = 0; j < n; ++j)

if (i != j && nums[i] + nums[j] == target)

++ans;

return ans;

}

};

一些工程上的优化

用string_view作为参数类型，减少一次string copy
先比较长度，再判断内容。
string_view.substr 是O(1)时间，和直接用strncmp比较内容是一样的。

优化后 3ms, 12.88MB

class Solution {

public:

int numOfPairs(vector<string>& nums, string_view target) {

const int n = nums.size();

int ans = 0;

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

for (int j = 0; j < n; ++j)

if (i != j

&& nums[i].size() + nums[j].size() == target.size()

&& target.substr(0, nums[i].size()) == nums[i]

&& target.substr(nums[i].size()) == nums[j])

++ans;

return ans;

}

};

花花酱 LeetCode 2296 Design a Text Editor

By zxi on April 2, 2025

方法1：双向链表来存储文本，迭代器指向光标所在的位置。加一个dummy head会使代码简单很多。

时间复杂度：TextEditor O(1) addText O(|text|) deleteText O(k) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)

由于每个字符需要创建一个节点（17+个字节），虽然没有超时，但实际工程中是不能使用这种方式的。

// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/

class TextEditor {

public:

TextEditor(): data_{'$'}, cursor_{begin(data_)} {}

void addText(string text) {

for (char c : text)

cursor_ = data_.insert(++cursor_, c);

}

int deleteText(int k) {

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

if (cursor_ == begin(data_)) return i;

data_.erase(cursor_--);

}

return k;

}

string cursorLeft(int k) {

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

if (cursor_ == begin(data_)) break;

cursor_--;

}

return getText();

}

string cursorRight(int k) {

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

if (cursor_ == prev(end(data_))) break;

cursor_++;

}

return getText();

}

private:

string getText() {

string ans;

auto it = cursor_;

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

if (it == begin(data_)) break;

ans += *it--;

}

reverse(begin(ans), end(ans));

return ans;

}

list<char> data_;

list<char>::iterator cursor_;

};

方法2: 用两个string来代表光标左边的字符串和光标右边的字符串。注：右边字符串是反转的。

左右两边的字符串只会增长（或者覆盖），不会缩短，这是用空间换时间。

删除的时候就是修改了长度而已，并没有缩短字符串，所以是O(1)的。
如果缩短的话需则要O(k)时间，还要加上内存释放/再分配的时间，应该会慢一些但不多。

移动光标的时候，就是把左边字符串的最后k个copy到右边的最后面，或者反过来。同样没有缩短，只会变长。

时间复杂度: TextEditor O(1) addText O(|text|) deleteText O(1) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)，n为构建的最长的字符串

// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/

class TextEditor {

public:

TextEditor() {}

void addText(string_view text) {

ensureSize(l, m + text.size());

copy(begin(text), end(text), begin(l) + m);

m += text.size();

}

int deleteText(int k) {

k = min(k, m);

m -= k;

return k;

}

string cursorLeft(int k) {

ensureSize(r, n + k);

for (k = min(k, m); k > 0; --k)

r[n++] = l[--m];

return getText();

}

string cursorRight(int k) {

ensureSize(l, m + k);

for (k = min(k, n); k > 0; --k)

l[m++] = r[--n];

return getText();

}

private:

inline void ensureSize(string& s, int size) {

if (s.size() < size)

s.resize(size);

}

string getText() const {

return string(begin(l) + m - min(m, 10), begin(l) + m);

}

string l;

string r;

int m = 0;

int n = 0;

};

花花酱 LeetCode 3498 Reverse Degree of a String

By zxi on March 30, 2025

送分题，简单仿真即可。

时间复杂度：O(n)
空间复杂度：O(1)

// https://zxi.mytechroad.com/blog/string/leetcode-3498-reverse-degree-of-a-string/

class Solution {

public:

int reverseDegree(string s) {

int ans = 0;

for (int i = 0; i < s.size(); ++i)

ans += ('z' - s[i] + 1) * (i + 1);

return ans;

}

};

花花酱 LeetCode 3029. Minimum Time to Revert Word to Initial State I

By zxi on February 5, 2024

You are given a 0-indexed string word and an integer k.

At every second, you must perform the following operations:

Remove the first k characters of word.
Add any k characters to the end of word.

Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.

Return the minimum time greater than zero required for word to revert to its initial state.

Example 1:

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2:

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3:

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

Constraints:

1 <= word.length <= 50
1 <= k <= word.length
word consists only of lowercase English letters.

Solution: Suffix ==? Prefix

Compare the suffix with prefix.

word = “abacaba”, k = 3
ans = 1, “~~aba~~caba” != “abac~~aba~~“
ans = 2, “~~abacab~~a” == “a~~bacaba~~“, we find it.

Time complexity: O(n * n / k)
Space complexity: O(1)

C++

class Solution {

public:

int minimumTimeToInitialState(string_view word, int k) {

const int n = word.length();

for (int i = 1; i * k < n; ++i) {

string_view t = word.substr(i * k);

if (t == word.substr(0, t.length())) return i;

}

return (n + k - 1) / k;

}

};

Posts published in “String”

花花酱 LeetCode 3517. Smallest Palindromic Rearrangement I

花花酱 LeetCode 2023. Number of Pairs of Strings With Concatenation Equal to Target

花花酱 LeetCode 2296 Design a Text Editor

花花酱 LeetCode 3498 Reverse Degree of a String

花花酱 LeetCode 3029. Minimum Time to Revert Word to Initial State I

Solution: Suffix ==? Prefix

C++