fastest algorithm to remove duplicate consecutive words in a string?

Question

Here's what I got:

string = 'John bought bought black paint for his black car'
words = string.split(' ')
duplicatelessWords = []
for (const word of words) {
  if (duplicatelessWords[duplicatelessWords.length - 1] !== word) {
    duplicatelessWords.push(word)
  }
}
duplicatelessString = duplicatelessWords.join(' ')

It should return "John bought black paint for his black car"

Is there a way to make it faster? I think I will need to use it many times in a row, sometimes on short strings, sometimes on large.

Kobi · Accepted Answer · 2019-12-14T01:46:32.803

You can use a regular expression:

const string = 'John bought bought black paint for his black black car';
const replaced = string.replace(/(\b\w+)(?: \1\b)+/g, '$1');
console.log(replaced);

I don't know if this the fastest option, but it does a single pass, and replaces only when actually required - so you won't split the string when there are no repeated words.

(\b\w+) - match a "word" made of alphanumeric characters. You may also use \S for non-spaces. See also Unicode support. The first word will be captured as group number 1.
(?: \1\b)+- find the same word we've captured (\1), repeated multiple times (+).
(?: ) is a logical group that is not captured.
\bis a word boundary, it ensures we don't allow partial matching inside words.
'$1' - once we find a repeated word, like "bought bought" we replace it with the first word: "bought".

Note that this works poorly when you have punctuation in your strings.

fastest algorithm to remove duplicate consecutive words in a string?

1 Answers1