# 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^2)
# space complexity: O(n)
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])