C) Shortest Substring
The main idea of my solution is that the answer should look like abb...bbbbbc: one character of type a, a block of characters of type b, and one character of type c. If we find all blocks of consecutive equal characters in our string, each candidate for the answer can be obtained by expanding a block to the left and to the right by exactly one character. So the total length of all candidates is O(n), and we can check them all.
Why does the answer look like abb...bbbbbc? If the first character of the substring appears somewhere else in it, it can be deleted. The same applies for the last character. So, the first and the last characters should be different, and should not appear anywhere else within the string. Since there are only three types of characters, the answer always looks like abb...bbbbbc.
from collections import defaultdict
num_tests = int(input())
for _ in range(num_tests):
string = input()
len_str = len(string)
ans = len_str + 1
freq = []
for i in range(len_str):
cur_char = string[i]
if len(freq) == 0 or freq[-1][0] != cur_char:
freq.append([cur_char, 1])
else:
freq[-1][1] += 1
freq_size = len(freq)
for i in range(1, freq_size - 1):
if freq[i - 1][0] != freq[i + 1][0]:
ans = min(ans, freq[i][1] + 2)
if ans == len_str + 1:
ans = 0
print(ans)
We can use the sliding window technique to solve this problem. We extend our window until we find all the three characters 1, 2, 3. And we will try to shorten the interval as much as we can but we have to make sure that the three numbers are present in the substring.
- Time Complexity: O(n)
- Space Complexity: O(n)
from collections import defaultdict
num_tests = int(input())
for _ in range(num_tests):
string = input()
len_str = len(string)
occurence = defaultdict(int)
left = 0
contained = 0
ans = len_str + 1
for right in range(len_str):
char_at_right = string[right]
occurence[char_at_right] += 1
if occurence[char_at_right] == 1:
contained += 1
while contained >= 3:
char_at_left = string[left]
occurence[char_at_left] -= 1
if occurence[char_at_left] == 0:
contained -= 1
left += 1
if left > 0:
ans = min(ans, right - left + 2)
if ans == len_str + 1:
ans = 0
print(ans)
D) Find K
Simulate with sample examples
Assume the array given was [A,B,C,D] what would be the pattern when you simulate it?
what if we deleted the variables in consecutive order like element at index 0 first then element at index 1, ... element at index — 1.
-
- let say we are given an array [A,B,C,D] and the optimal order of removing elements is always removing element at index 0 to see the pattern.
-
- first we delete A and subtract from the rest
-
-
- [B — A, C — A, D — A]
-
-
- Then we delete the next sequence which is B — A
-
-
- [C — A — (B — A), D — A — (B — A)]
-
-
-
- which simplifies to [C — B, D — B]
-
-
- Finally we delete the next sequence which is C — B
-
-
- [D — B — (C — B)]
-
-
-
- which simplifies to [D — C]
-
- So we can see that we only need two number whose difference is equal to k. so basically we need to find two numbers that meet the condition and print YES and if we can't get print NO
def solve():
n , k = map(int , input().split())
nums = list(map(int, input().split()))
i = 0
j = 1
found = False
nums.sort()
while not found and j < n:
difference = nums[j] - nums[i]
if difference == k:
found = True
elif difference > k:
i += 1
else:
j += 1
if found:
print("YES")
else:
print("NO")
def main():
t = int(input())
for _ in range(t):
solve()
main()
def solve():
n, k = map(int, input().split())
a = list(map(int, input().split()))
occured = set()
ok = False
i = 0
while not ok and i < n:
x = a[i] - k
y = a[i] + k
if x in occured:
ok = True
if y in occured:
ok = True
occured.add(a[i])
i += 1
if ok:
print("YES")
else:
print("NO")
def main():
t = int(input())
for i in range(t):
solve()
main()