Find Duplicate Words

A very common interview challenge is to determine how often words appear in a given string or set of strings. Here's a version of this: return a list of duplicate words in a sentence.

For example, given 'The dog is the best', returns ["the"].

Likewise, given 'Happy thanksgiving, I am so full', you would return an empty array. This is because there are no duplicates in the string.

Constraints

• The total length of the string <= 100000
• The string will consist of ASCII characters (may be some or all)
• Expected time complexity : O(n) where n are the number of words in the string
• Expected space complexity : O(n)

```js
function findDuplicates(str) {
	const dupes = [];
  // fill in

	return dupes;
}
```
```java
public class Main {
    public static void main(String[] args) {
        // driver code
    }
    
    public static List<Character> findDuplicates(String str) {
        List<Character> dupes = new ArrayList<>();
        // fill in

        return dupes;
    }
}
```
```javascript
function findDuplicates(str) {
	  let dupes = [];
    // fill in

	  return dupes;
}
```
```python
def find_duplicates(str):
    dupes = []
    # fill in

    return dupes
```
```cpp
#include <vector>

std::vector<char> findDuplicates(std::string str) {
    std::vector<char> dupes;
    // fill in

    return dupes;
}
```
```csharp
public class Program
{
    public static void Main()
    {
        // driver code
    }

    public static List<char> FindDuplicates(string str)
    {
        List<char> dupes = new List<char>();
        // fill in

        return dupes;
    }
}
```
```go
package main

func findDuplicates(str string) []rune {
	var dupes []rune
	// fill in

	return dupes
}

func main() {
	// driver code
}
```

The Foundation: Understanding the Problem

To find duplicate words in a sentence, we need a systematic approach for analyzing the occurrences of each word. Essentially, our task is to examine each word in the given string and keep a tab on how often it shows up.

Step 1: Tokenizing the Sentence into Words

What Does Tokenizing Mean?

Tokenization is the process of converting a sequence of text into individual "tokens" or units. In our context, this means splitting the given sentence into individual words.

How to Tokenize?

We can start by converting the entire string to lowercase to make our function case-insensitive. Then, we'll use the split function to break it into an array of words.

split_s = s.lower().split(' ')

String[] split_s = s.toLowerCase().split(" ");

let split_s = s.toLowerCase().split(' ');

std::string s_lower = s;
std::transform(s_lower.begin(), s_lower.end(), s_lower.begin(), ::tolower);
std::istringstream iss(s_lower);
std::vector<std::string> split_s{std::istream_iterator<std::string>{iss}, std::istream_iterator<std::string>{}};

string[] split_s = s.ToLower().Split(' ');

sLower := strings.ToLower(s)
splitS := strings.Split(sLower, " ")

```py
s = "Original String"
split_s = s.lower().split(' ')

occurrences = {}

for word in split_s:
	if word not in occurrences:
		occurrences[word] = 1
	else:
		occurrences[word] += 1

print(occurrences)
```
```java
class Main {
  public static void main(String[] args) {
    String s = "Original String";
    String[] splitS = s.toLowerCase().split(" ");
    Map<String, Integer> occurrences = new HashMap<>();

    for (String word : splitS) {
      if (!occurrences.containsKey(word)) {
        occurrences.put(word, 1);
      } else {
        occurrences.put(word, occurrences.get(word) + 1);
      }
    }

    System.out.println(occurrences);
  }
}
```
```javascript
let s = "Original String";
let splitS = s.toLowerCase().split(" ");
let occurrences = {};

for (let word of splitS) {
  if (!occurrences.hasOwnProperty(word)) {
    occurrences[word] = 1;
  } else {
    occurrences[word]++;
  }
}

console.log(occurrences);
```
```cpp
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>

int main() {
    std::string s = "Original String";
    std::transform(s.begin(), s.end(), s.begin(), ::tolower);
    std::istringstream iss(s);
    std::map<std::string, int> occurrences;
    std::string word;

    while (iss >> word) {
        if (occurrences.find(word) == occurrences.end()) {
            occurrences[word] = 1;
        } else {
            occurrences[word]++;
        }
    }

    for (const auto &pair : occurrences) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
```
```csharp
using System;
using System.Collections.Generic;

class Program {
  public static void Main(string[] args) {
    string s = "Original String";
    string[] splitS = s.ToLower().Split(' ');
    Dictionary<string, int> occurrences = new Dictionary<string, int>();

    foreach (var word in splitS) {
      if (!occurrences.ContainsKey(word)) {
        occurrences[word] = 1;
      } else {
        occurrences[word]++;
      }
    }

    foreach (KeyValuePair<string, int> entry in occurrences) {
      Console.WriteLine(entry.Key + ": " + entry.Value);
    }
  }
}
```
```go
package main

import (
	"fmt"
	"strings"
)

func main() {
	s := "Original String"
	splitS := strings.Fields(strings.ToLower(s))
	occurrences := make(map[string]int)

	for _, word := range splitS {
		_, ok := occurrences[word]
		if !ok {
			occurrences[word] = 1
		} else {
			occurrences[word]++
		}
	}

	for key, value := range occurrences {
		fmt.Println(key, ":", value)
	}
}
```

Step 2: Counting the Words Using a HashMap

Why a HashMap?

A HashMap provides an efficient way to store key-value pairs. In our case, the word will be the key, and its frequency will be the value. This will enable us to look up the frequency of a word in constant time.

How to Count?

We'll initialize an empty HashMap (or an object in JavaScript, or a dictionary in Python) to store the occurrences of each word. Let's call this HashMap occurrences.

Code Snippet for Counting

Here's how you can populate the occurrences HashMap:

occurrences = {}
for word in split_s:
    if word in occurrences:
        occurrences[word] += 1
    else:
        occurrences[word] = 1

Map<String, Integer> occurrences = new HashMap<>();
for(String word : split_s) {
    if(occurrences.containsKey(word)) {
        occurrences.put(word, occurrences.get(word) + 1);
    } else {
        occurrences.put(word, 1);
    }
}

let occurrences = {};
for(let word of split_s) {
    if(word in occurrences) {
        occurrences[word]++;
    } else {
        occurrences[word] = 1;
    }
}

std::map<std::string, int> occurrences;
for(auto& word : split_s) {
  if(occurrences.count(word) > 0) {
      occurrences[word]++;
  } else {
      occurrences[word] = 1;
  }
}

Dictionary<string, int> occurrences = new Dictionary<string, int>();
foreach(var word in split_s) {
    if (occurrences.ContainsKey(word)) {
        occurrences[word]++;
    } else {
        occurrences[word] = 1;
    }
}

occurrences := make(map[string]int)
for _, word := range split_s {
    _, exists := occurrences[word]
    if exists {
        occurrences[word]++
    } else {
        occurrences[word] = 1
    }
}

Step 3: Identifying Duplicate Words

What are Duplicate Words?

Duplicate words are the keys in our HashMap with a value greater than 1, as these words have appeared more than once in the sentence.

How to Find Them?

We can loop through our occurrences HashMap to find these duplicates.

duplicates = []
for word, count in occurrences.items():
    if count > 1:
        duplicates.append(word)

ArrayList<String> duplicates = new ArrayList<>();
for(Map.Entry<String, Integer> entry : occurrences.entrySet()){
    String key = entry.getKey();
    Integer value = entry.getValue();
    if(value > 1){
        duplicates.add(key);
    }
}

let duplicates = [];
for(let [word, count] of Object.entries(occurrences)) {
    if(count > 1) {
        duplicates.push(word);
    }
}

std::vector<std::string> duplicates;
for(auto& it: occurrences) {
    if(it.second > 1){
        duplicates.push_back(it.first);
    }
}

List<string> duplicates = new List<string>();
foreach (KeyValuePair<string, int> entry in occurrences)
{
    if (entry.Value > 1){
        duplicates.Add(entry.Key);
    }
}

duplicates := make([]string, 0)
for word, count := range occurrences {
    if count > 1 {
        duplicates = append(duplicates, word)
    }
}

Step 4: Unveiling the Duplicates

Identifying Duplicates Made Easy

After painstakingly counting the frequency of each word, finding duplicates becomes a cakewalk. All we have to do is sift through our occurrences HashMap and pinpoint the words that have a frequency of 2 or more. These are our coveted duplicates.

Code Snippet for Identifying Duplicates

Here's how you can extract the duplicates from our occurrences HashMap:

duplicates = []
for word, count in occurrences.items():
    if count > 1:
        duplicates.append(word)

ArrayList<String> duplicates = new ArrayList<>();
for (Map.Entry<String, Integer> entry : occurrences.entrySet()) {
    if (entry.getValue() > 1) {
        duplicates.add(entry.getKey());
    }
}

let duplicates = [];
for (let [word, count] of Object.entries(occurrences)) {
    if (count > 1) {
        duplicates.push(word);
    }
}

std::vector<std::string> duplicates;
for (auto& kv : occurrences) {
    if (kv.second > 1) {
        duplicates.push_back(kv.first);
    }
}

List<string> duplicates = new List<string>();
foreach (KeyValuePair<string, int> occurrence in occurrences)
{
    if (occurrence.Value > 1)
    {
        duplicates.Add(occurrence.Key);
    }
}

duplicates := []string{}
for word, count := range occurrences {
    if count > 1 {
        duplicates = append(duplicates, word)
    }
}

Analyzing the Complexity of Our Final Solution

Time Complexity Revisited

Let n be the number of words in our input string s.

1. Populating the occurrences HashMap took O(n) time.
2. Traversing the occurrences HashMap to identify duplicates also takes O(n) time.

Summing these up, our algorithm works in linear O(n) time, which is remarkably efficient.

Space Complexity Revisited

We've used a HashMap (occurrences) to store the frequency of each word, and a list (duplicates) to store the duplicate words. In a worst-case scenario, each word in the sentence is unique, making our space complexity linear O(n).

```py
s = "Original String Original String"
split_s = s.lower().split(' ')

occurrences = {}

for word in split_s:
	if word not in occurrences:
		occurrences[word] = 1
	else:
		occurrences[word] += 1

dupes = []
for k in occurrences:
	if occurrences[k] == 2:
		dupes.append(k)

print(dupes)
```
```java
import java.util.*;

public class Main {
    public static void main(String[] args){
        String s = "Original String Original String";
        String[] split_s = s.toLowerCase().split(" ");

        Map<String, Integer> occurrences = new HashMap<>();

        for (String word : split_s) {
            if (!occurrences.containsKey(word)) {
                occurrences.put(word, 1);
            } else {
                occurrences.put(word, occurrences.get(word) + 1);
            }
        }

        List<String> dupes = new ArrayList<>();
        for (String k : occurrences.keySet()) {
            if (occurrences.get(k) == 2) {
                dupes.add(k);
            }
        }

        System.out.println(dupes);
    }
}
```
```javascript
let s = "Original String Original String";
let split_s = s.toLowerCase().split(' ');

let occurrences = {};

for (let word of split_s) {
    if (!occurrences[word]) {
        occurrences[word] = 1;
    } else {
        occurrences[word] += 1;
    }
}

let dupes = [];
for (let k in occurrences) {
    if (occurrences[k] === 2) {
        dupes.push(k);
    }
}

console.log(dupes);
```
```cpp
#include <iostream>
#include <sstream>
#include <map>
#include <vector>
#include<bits/stdc++.h>

using namespace std;

int main() {
    string s = "Original String Original String";
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    stringstream ss(s);
    string word;
    map<string, int> occurrences;

    while (ss >> word) {
        occurrences[word]++;
    }

    vector<string> dupes;
    for (auto& k : occurrences) {
        if (k.second == 2) {
            dupes.push_back(k.first);
        }
    }

    for (string dupe: dupes){
         cout << dupe << " ";
    }
    return 0;

}
```
```csharp
using System;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        string s = "Original String Original String";
        string[] split_s = s.ToLower().Split(' ');

        Dictionary<string, int> occurrences = new Dictionary<string, int>();

        foreach (string word in split_s) {
            if (!occurrences.ContainsKey(word)) {
                occurrences[word] = 1;
            } else {
                occurrences[word] += 1;
            }
        }

        List<string> dupes = new List<string>();
        foreach (string k in occurrences.Keys) {
            if (occurrences[k] == 2) {
                dupes.Add(k);
            }
        }

        Console.WriteLine(string.Join(", ", dupes));
    }
}
```
```go
package main

import (
	"strings"
	"fmt"
)

func main() {
	s := "Original String Original String"
	split_s := strings.Fields(strings.ToLower(s))

	occurrences := make(map[string]int)

	for _, word := range split_s {
		occurrences[word]++
	}

	var dupes []string
	for k, v := range occurrences {
		if v == 2 {
			dupes = append(dupes, k)
		}
	}

	fmt.Println(dupes)
}
```

One Pager Cheat Sheet

• This challenge requires returning a list of duplicate words in a sentence that consists of ASCII characters with a time complexity of O(n) and a space complexity of O(n).
• We can use a hashmap (or JS object or Python dict) to store each word's frequency by looping through each one in the array and recording its occurrence.
• We can easily find the duplicates by counting the occurrences of each word and looking for those with 2!