Because Strings are Immutable in Python, Can we actually remove duplicates in Place?

Question

Below fails because strings are immutable. I am trying to remove duplicates in place. Is there a better way to do this?

def remove_duplicates_2(word):
  write_index = 0

  for i in range(len(word)):
    found = False

    for j in range(0, write_index):
      if word[i] == word[j]:
        found = True
        break

    if found == False:
      word[write_index] = word[i]
      write_index += 1

    return word

What is it that you exactly want to do? Do you want to remove duplicate alphabets in a word? — taurus05, Feb 04 '19 at 06:18
Given 'abbcccddd', return 'abcd'. (Remove Duplicates in Place) — Zacharia Mwangi, Feb 04 '19 at 06:42

Ouroborus · Answer 1 · 2019-02-04T06:23:04.047

1

No, not in Python. Every time you do something that seems like you "modify" a string, you're actually creating a new, immutable string.

Depending on the reasons for or intent of the "in place" requirement, you may be able to convert the string to another type (list of characters, StringIO, etc.), modify that, then convert it back to a string.

Honestly, this sounds like an interview question. Python wouldn't be an appropriate language to use for the answer due to this constraint. The interviewer would likely be expecting you to use C or C++.

edited Feb 04 '19 at 06:23

answered Feb 04 '19 at 06:06

Ouroborus

16,237
4
39
62

Could you share an example? – Zacharia Mwangi Feb 04 '19 at 06:10
@ZachariaMwangi See the answers to [this question](https://stackoverflow.com/questions/1228299/change-one-character-in-a-string). – Ouroborus Feb 04 '19 at 06:18

taurus05 · Answer 2 · 2019-02-04T12:01:19.670

There is nothing, you can do to remove duplicates from a string in place. It is because strings are immutable in Python. To do so, you'll have to do something as follows:

Create a list of alphabets from the string.
Create a stack.
If the stack is empty, push the current element of the list into the stack.
If the topmost element of the stack is the same as the current element of the list, then don't push it, just move to the next element in the list.
If it is not the same as the topmost element, then push it.
After having done all the push operations (once iterated over all the list elements), reverse the contents of the stack and join its contents to form a new string.
Now the resulting string doesn't contain any duplicates.

blueenvelope · Answer 3 · 2019-02-04T07:28:28.497

If you want to remove all but the first occurrence of each letter in a word,

e.g millennium -> milenu

you can do something like the below:

def remove_duplicate_letters(word):
    result = ""
    for c in word:
        if c not in result:
            result += c
    return result

As you correctly note this is not 'in place'. The string object that variable 'word' points to is unchanged. It can not be changed because string objects are immutable in Python. Instead a new string object is created. In fact many of them. One for the empty string. Then again when we add the first letter, 'm'. And again when we add 'i' and so on.

Be careful. Again strings are immutable. While it looks like we change 'result', what is going on in memory is we create a new string object each loop and change where the variable 'result' points.

Because Strings are Immutable in Python, Can we actually remove duplicates in Place?

3 Answers3