소문자만 포함된 문자열 s가 있다고 가정하고 다음 규칙을 충족하는 s의 비어 있지 않은 부분 문자열의 최대 수를 찾아야 합니다.
-
부분 문자열이 겹치지 않습니다.
-
특정 문자 ch를 포함하는 부분 문자열은 ch의 모든 발생도 포함해야 합니다.
우리는 이 두 조건을 충족하는 부분 문자열의 최대 수를 찾아야 합니다. 동일한 수의 하위 문자열을 가진 솔루션이 둘 이상 있는 경우 총 길이가 최소인 솔루션을 반환합니다.
따라서 입력이 s ="pqstpqqprrr"과 같으면 조건을 충족하는 가능한 모든 하위 문자열이 [ "pqstpqqprrr", "pqstpqqp"이기 때문에 출력은 ["s","t","rrr"]이 됩니다. , "st", "s", "t", "rrr"]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
right :=s의 오른쪽부터 모든 개별 문자 ch의 인덱스 위치 목록 정렬
-
왼쪽 :=오른쪽의 모든 i에 대한 문자 s[i]의 인덱스 목록
-
has :=빈 목록, gen :=빈 목록
-
범위 0에서 오른쪽 크기 - 1에 있는 i의 경우 수행
-
gen
끝에 s[right[i]]의 새 문자 세트를 삽입합니다. -
has
끝에 있는 s[from index (left[i] + 1 to right[i]-1] - gen의 마지막 항목)의 하위 문자열에서 새 문자 세트를 삽입합니다. -
범위 크기의 j에 대해 - 2에서 0, 1 감소, 수행
-
(has AND gen[j]의 마지막 항목) 및 (has[j] AND 마지막 항목인 gen)이 0이 아닌 경우
-
gen의 마지막 항목 :=gen의 마지막 항목 또는 gen[j]
-
has의 마지막 항목 :=(has OR has[j]의 마지막 항목) - gen의 마지막 항목
-
has[j], gen[j]
제거
-
-
-
-
res :=새 목록, p_right :=-1
-
범위 0에서 has - 1의 ind에 대해 수행
-
l :=s[i]가 gen[ind]에 있는 경우 왼쪽의 모든 i에 대한 요소 목록의 최소값
-
r :=s[i] in gen[ind]]
오른쪽에 있는 모든 i에 대한 요소 목록의 최대값 -
p_right
-
res
의 끝에 s[인덱스 l에서 r까지]의 부분 문자열 삽입 -
p_right :=r
-
-
-
반환 해상도
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s):
right = sorted([s.rindex(ch) for ch in set(s)])
left = [s.index(s[i]) for i in right]
has, gen = [], []
for i in range(len(right)):
gen.append(set(s[right[i]]))
has.append(set(s[left[i] + 1:right[i]]) - gen[-1])
for j in range(len(has) - 2, -1, -1):
if (has[-1] & gen[j]) and (has[j] & gen[-1]):
gen[-1] = gen[-1] | gen[j]
has[-1] = (has[-1] | has[j]) - gen[-1]
del has[j], gen[j]
res, p_right = [], -1
for ind in range(len(has)):
l = min([i for i in left if s[i] in gen[ind]])
r = max([i for i in right if s[i] in gen[ind]])
if p_right < l:
res.append(s[l : r + 1])
p_right = r
return res
s = "pqstpqqprrr"
print(solve(s))인 경우 입력
"pqstpqqprrr"
출력
['s', 't', 'rrr']