Anagrams

Problem Statement

Given two strings, a and b, that may or may not be of the same length, determine the minimum number of character deletions required to make a and b anagrams.

Any characters can be deleted from either of the strings.

Questions to ask

Characters in the string are only lowercase? Yes

Can special characters exist in the string? No

Solution

The solution is pretty straightforward. Knowing that the a character is a number from 0 to 255, make an array to count the frequency of characters from the first string. Now you will loop trough the second array and remove the character from the array that count the frequency. Loop through the frequency array and sum the absolute value of each index to a result variable.

int getMinimumDeletionsToAnagram(string s1, string s2){
  vector<int> count(256,0);
  int result =0;
  for(auto c:s1){
    count[c-'a']++;
  }

  for(auto c:s2){
    count[c-'a']--;
  }

  for(auto val : count){
    result+=abs(val);
  }

  return result;
}

Time Complexity: O(n)

Space Complexity: O(1)

question from HackerRank