Amazon interview
Summary
I faced a challenging problem during my Amazon interview where I had to remove the shortest substring from a string of 'a', 'b', and 'c' to balance their counts. The solution required careful tracking of character counts and efficient substring removal.
Full Experience
Given a string consisting of only "a", "b", "c", remove the shortest substring such that the remaining string has the same count of 'a', 'b', and 'c'.
Eg: "abcbbabc"
remove bb and you get
abcabc
so ans = 6
Eg2: "abcbbccabc"
ans = 6
Solution:
We try to select block (i,j) whose removal results in ans:
We can calculate total_a and total_b to calculate excess a and b.
total_a = 0 total_b = 0 for i in s: if i == 'a': total_a += 1 elif i == 'b': total_b += 1 else: total_b-=1 total_a -=1
a_count = 0 b_count = 0 counter = 0
print(total_a, total_b)
d[(0,0)]=-1 counter = n for idx, i in enumerate(s): if i=='a': a_count+=1 elif i=='b': b_count+=1 else: a_count-=1 b_count-=1
d[(a_count, b_count)] = idx
to_be_removed = (a_count - total_a, b_count - total_b)
# print(idx, to_be_removed, d)
if to_be_removed in d:
counter = min(counter, (idx - d[to_be_removed]))
return counter
def solve(s): return len(s) - min_remove_for_equal_abc(s)
s = "abcbb" res = solve(s) print(res)
Interview Questions (1)
Given a string consisting of only 'a', 'b', 'c', remove the shortest substring such that the remaining string has the same count of 'a', 'b', and 'c'. For example, in the input 'abcbbabc', removing 'bb' results in 'abcabc', which has equal counts of each character. The solution requires calculating the total counts of each character and then determining the shortest substring to remove to balance the counts.