Last Updated on 2021-12-13 by Clay
題目
The power of the string is the maximum length of a non-empty substring that contains only one unique character. Given a string s, return the power of s.
Example 1:
Input: s = "leetcode" Output: 2 Explanation: The substring "ee" is of length 2 with the character 'e' only.
Example 2:
Input: s = "abbcccddddeeeeedcba" Output: 5 Explanation: The substring "eeeee" is of length 5 with the character 'e' only.
Example 3:
Input: s = "triplepillooooow" Output: 5
Example 4:
Input: s = "hooraaaaaaaaaaay" Output: 11
Example 5:
Input: s = "tourist" Output: 1
這題目的意思就是，給定一字串，我們要找到最長的相同字元子字串並回傳。
解題思路
這題真不愧是 Easy… 我愣是沒想出除了暴力法之外的任何解決方案哈哈哈。
所以我的方法就是 Brute Force，直接一個個字元讀過去，同時跟上一個字元做比較，相同的話就長度加一、不同的就重新計算。
這個方法還是 O(n) 的時間複雜度、O(1) 的空間複雜度。
C++ 範例程式碼
class Solution {
public:
int maxPower(string s) {
// Init
int n = 1;
int temp_n = 1;
// Match
for (int i=1; i<s.size(); ++i) {
if (s[i] == s[i-1]) {
++temp_n;
}
else {
temp_n = 1;
}
// Max
n = max(n, temp_n);
}
return n;
}
};Python 範例程式碼
class Solution:
def maxPower(self, s: str) -> int:
# Init
n = 1
temp_n = 1
# Match
for i in range(1, len(s)):
if (s[i] == s[i-1]):
temp_n += 1
else:
temp_n = 1
# Max
n = max(n, temp_n)
return n