Find Common Characters Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the classic “Find Common Characters” problem! It’s like trying to find common ground with your friends when deciding on a restaurant. You know, when everyone has their own preferences, and you end up at a place that serves food no one really likes. In this problem, you’re given an array of strings (think of them as your friends’ food preferences), and your task is to find the characters that appear in every single string (or restaurant) in the array.

So, if you have words like “bella”, “label”, and “roller”, the common characters would be ‘e’, ‘l’, and ‘l’. But if your friends are picky eaters and one of them only likes “apple”, well, good luck finding a common dish!

Code Solution


class Solution {
  public List commonChars(String[] words) {
    List ans = new ArrayList<>();
    int[] commonCount = new int[26];
    Arrays.fill(commonCount, Integer.MAX_VALUE);

    for (final String word : words) {
      int[] count = new int[26];
      for (final char c : word.toCharArray())
        ++count[c - 'a'];
      for (int i = 0; i < 26; ++i)
        commonCount[i] = Math.min(commonCount[i], count[i]);
    }

    for (char c = 'a'; c <= 'z'; ++c)
      for (int i = 0; i < commonCount[c - 'a']; ++i)
        ans.add(String.valueOf(c));

    return ans;
  }
}

Approach

The approach taken in this solution is quite straightforward. We maintain an array commonCount to keep track of the minimum occurrences of each character across all words. For each word, we count the occurrences of each character and update the commonCount array accordingly. Finally, we construct the result list by adding each character the number of times it appears in all words.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of words and M is the maximum length of a word.
Space Complexity	O(1), since the size of the `commonCount` array is fixed at 26 (for each letter of the alphabet).

Real-World Example

Imagine you and your friends are trying to decide on a movie to watch. Each friend has their own list of favorite movies. The common movies that everyone can agree on are like the common characters in our problem. If one friend only likes action movies, and another only likes romantic comedies, good luck finding a movie that everyone will enjoy!