Remove Duplicates

Coding Skill Exercise #24

Remove Duplicates

Write a method to remove duplicate characters from a given string.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here. https://codingskill.biz

title: Remove Duplicates excerpt: Solution for a common string interview question. tags: two-pointers-moving-in-same-direction two-pointers-left-to-right-scan read-and-write-pointers set-to-track

A set is used to keep track of which letters we have already seen in the input string. Two pointers are used to solve this problem, one pointer for reading and one pointer for writing. The read and write pointers are used to return a substring that consists of only unique letters.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

require 'set'

def remove_duplicates(string)
  set = Set.new
  
  write_index = 0
  read_index = 0
  
  while read_index < string.size
    unless set.include?(string[read_index])
      set.add((string[read_index]))
      
      string[write_index] = string[read_index]
      write_index += 1
    end
    
    read_index += 1
  end
  
  string[0, write_index]
end

p remove_duplicates('abbabcddbabcdeedebc')

Alternative approach where we do not use additional space:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def remove_duplicates(s)
  write = 0
  
  for i in (0..s.size - 1)
    found = false

    for j in (0..write - 1)
      if s[i] == s[j]
        found = true
        break
      end
    end

    unless found
      s[write] = s[i]
      write += 1
    end
  end
  
  s[0, write]
end

p remove_duplicates('abbabcddbabcdeedebc')

Building Blocks

• Set to Track Unique Letters
• Read and Write Pointers
• Two Pointers Moving in Same Direction