| 12345678910111213141516171819202122232425262728293031323334 |
- # Design an algorithm that removes the duplicate characters in a string
- # without using additional buffer.
- import pytest
- def test_remove_duplicates():
- case1 = ''
- case2 = 'a'
- case3 = 'asdfghjkl'
- case4 = 'aasdee'
- assert remove_duplicates(case1) == ''
- assert remove_duplicates(case2) == 'a'
- assert remove_duplicates(case3) == 'asdfghjkl'
- assert remove_duplicates(case4) == 'asde'
- pytest.main()
- # use two indicies to track non-duplicates in place.
- # time complexity: O(n)
- # space complexity: O(1)
- def remove_duplicates(input):
- len_input = len(input)
- if len_input <= 1:
- return input
- else:
- list_input = list(input)
- len_non_dup = 1
- for j in range(1, len_input):
- if list_input[j] in list_input[:len_non_dup]:
- pass
- else:
- list_input[len_non_dup] = input[j]
- len_non_dup += 1
- return ''.join(list_input[:len_non_dup])
|
