連三碼相同的最大值 Leetcode #2264 Largest 3-SameDigit Num in String

Nick Hillier on Unsplash

題目敘述

題目會給我們一個字串，要求我們連三碼相同的數字，最大值是多少?

例如 給定輸入="1111222555333"，最大值是555

如果無解，則返回空字串""

英文版的題目敘述在這裡

測試範例

Example 1:

Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

Example 2:

Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

約束條件

Constraints:

• 3 <= num.length <= 1000
• num only consists of digits.

演算法

依照題意，從左到右掃描，紀錄連續三碼相同的字元，如果比之前的還大，就更新為最大值。

實作上要留意的就是:

1. 迭代的下標，小心不要超出界外。
2. 題目給的輸入是字串，我們計算過程中會轉成int整數型別，最後輸出答案時，記得轉換回字串的形式。

程式碼

class Solution(object):
　def largestGoodInteger(self, num):
　　
　　largest = -1
　　
　　for i in range(2, len(num)):

　　　if num[i] == num[i-1] and num[i-1] == num[i-2]:
　　　　cur_digit = int(num[i])
　　　　largest = max(largest, cur_digit)

　　if largest == -1:
　　　return ""

　　# Largest 3 same digit number in terms of string
　　return str(largest) * 3

複雜度分析

時間複雜度: O(n)

線性掃描，從右到左掃描每個字元，總共耗時O(n)

空間複雜度: O(1)

所使用到的都是固定尺寸的臨時變數，佔用空間為常數級別O(1)

Reference:

[1] Python O(n) by iteration [w/ Comment] - Largest 3-Same-Digit Number in String - LeetCode