Description
You are given a string num representing a large integer. An integer is good if it meets the following conditions:
It is a substring of num with length 3.
It consists of only one unique digit.
Return the maximum good integer as a string or an empty string "" if no such integer exists.
A substring is a contiguous sequence of characters within a string.
There may be leading zeroes in num or a good integer.
Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".
Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.
Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.
3 <= num.length <= 1000
num only consists of digits.
Solution
Sliding window
A window could expand only when: a). the new element is the same, b) the length of the window is smaller than 3.
Since right is the new element in the window, and left is also in the window, the length of the window is right - left + 1.
o
(
n
)
o(n)
o
(
1
)
o(1)
o(1)
Enumerate
Since the answer is only 000, 111, 222, ..., we could just enumerate from 999 to 000. If it exists in the num then return, otherwise return an empty string.
o
(
n
)
o(n)
o(n) because of in
Space complexity:
o
(
1
)
o(1)
o(1)
Code
Sliding window
class Solution:
def largestGoodInteger(self, num: str) -> str:
left = 0
res_num = -1
for right in range(len(num)):
while num[left] != num[right] or right - left + 1 > 3:
left += 1
if right - left + 1 == 3:
res_num = max(res_num, int(num[left: right + 1]))
if res_num == -1:
res = ''
elif res_num == 0:
res = '000'
else:
res = str(res_num)
return res
Enumerate
class Solution:
def largestGoodInteger(self, num: str) -> str:
for i in range(9, -1, -1):
cur_char = str(i) * 3
if cur_char in num:
return cur_char
return ''
原文地址:https://blog.csdn.net/sinat_41679123/article/details/134775418
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_47944.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
