sjjpo2002
BAN USERPython 3 implementation:
def remove_3_consecutives(s):
output = []
counter = 1
flag_to_remove = None
for char in s:
if not flag_to_remove == char:
flag_to_remove = None
if len(output):
if not char == output[-1]:
output.append(char)
counter = 1
else:
if counter < 2:
counter += 1
output.append(char)
else:
del output[-2:]
flag_to_remove = char
counter = 1
else:
output.append(char)
flag_to_remove = None
return output
if __name__ == '__main__':
s = 'ABCCCCBBA'
remove_3_consecutives(s)
Like others mentioned using a stack and a dictionary of open and close characters this is trivial to implement. O(n) Python 3 implementation:
def validate_string(s, brackets_dict):
stack = []
open_bracket = set(brackets_dict.keys())
close_bracket = set(brackets_dict.values())
open = False
for char in s:
if not open:
if char in close_bracket:
return False
open = True
stack.append(brackets_dict[char])
else:
if char in open_bracket:
stack.append(brackets_dict[char])
else:
if not char == stack.pop():
return False
if len(stack) == 0:
open = False
return True
if __name__ == '__main__':
s = '{{[]}}'
validate_string(s, {'{': '}', '[': ']'})
I see some people use the Sum to check if it is a sequence. While Sum is easily commutable knowing the min (first in seq) and max (last in seq) elements by n/2*[min + max]. Even if you match the sum it doesn't mean you have a sequence. Like the two sequences below:
seq1 = 1, 3, 5, 7, 9 (True)
seq2 = 1, 4, 5, 6, 9 (False)
As mentioned by small challenges the best you can get is O(n):
1. Go tru the elements to find min and max and build a hashmap
2. in a loop check if all the elements of the expected sequence exist in the hashmap
O(n) time with extra O(n) space
recursive Python 3 solution:
- sjjpo2002 November 09, 2018