Strings: Making Anagrams

Given two strings,  and , that may or may not be of the same length, determine the minimum number of character deletions required to make  and  anagrams. Any characters can be deleted from either of the strings.

Input Format

The first line contains a single string, .
The second line contains a single string, .

Constraints

• It is guaranteed that  and  consist of lowercase English alphabetic letters (i.e.,  through ).

Output Format

Print a single integer denoting the number of characters you must delete to make the two strings anagrams of each other.

Sample Input

cde
abc

Sample Output

4

Explanation

We delete the following characters from our two strings to turn them into anagrams of each other:

1. Remove d and e from cde to get c.
2. Remove a and b from abc to get c.

We must delete  characters to make both strings anagrams, so we print  on a new line.

Algorithm:

One picture tells it all:

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static int countDiff(int[] first, int[] second){ if( first.length != second.length ){ return -1; } int count = 0; for(int i = 0; i < first.length; i++ ){ int diff = Math.abs(first[i] - second[i]); count += diff; } return count; } public static int[] countChars(String str){ int[] result = new int[26]; int offset = (int) 'a'; for(int i=0; i < str.length(); i++ ){ char cc = str.charAt(i); result[cc-offset]++; } return result; } public static int numberNeeded(String first, String second) { int[] countF = countChars(first); int[] countS = countChars(second); return countDiff(countF, countS); } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); } }

LeetCode Summary

Github project for my local compiles

[table color="theme3"] [row] [heading]#[/heading] [heading]Problem Description[/heading] [/row] 

[row] [col]438[/col] [col]Find All Anagrams in a String[/col] [/row]
[row] [col]189[/col] [col]Rotate Array[/col] [/row]
[row] [col]141[/col] [col]Linked List Cycle[/col] [/row]
[row] [col]77[/col] [col]Combinations[/col] [/row]
[row] [col]48[/col] [col]Rotate Image[/col] [/row]
[row] [col]46[/col] [col]Permutations[/col] [/row]

 [/table]

Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abcdabc" p: "abc"

Output:
[0, 4]

Explanation:
The substring with start index = 0 is "abc", which is an anagram of "abc".
The substring with start index = 4 is "abc", which is an anagram of "abc".

Algorithm:

The idea is to convert the string to the counter array. Take Example 2 for example:
                   a , b, c, ....., z
p: "abc" => [1, 1, 1, ....., 0]   as pCount     // means 'a' appears once, 'b' appears once

To initialize, we take the first slice of window from s: "abcdabc" which is "abc"

window: "abc" => [1, 1, 1, ...., 0] as windowCount

if pcCount == windowCount then we know at index 0 we found a match result = [0]

We apply the same idea to the rest of the sliding windows: bcd, cda, dab, abc

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

class Solution { int countEqual(int[] window, int[] target){ // Make sure window and target have the same length if( window.length != target.length ) return -1; int count = 0; for(int i=0; i < window.length; i++){ int diff = Math.abs(window[i] - target[i]); count += diff; } // If return zero, means window and target are identical return count; } int[] countChars(String str){ int[] counter = new int[26]; int offset = (int) 'a'; for(int i=0; i < str.length(); i++){ char cc = str.charAt(i); counter[cc-offset]++; } return counter; } public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new LinkedList<Integer>(); if( p.length() > s.length() ) return result; int[] pCount = countChars(p); // char count view of the first window int[] windowCount = countChars(s.substring(0, p.length())); if( countEqual(pCount, windowCount) == 0) result.add(0); for(int i = 1; i < s.length()-p.length()+1; i++) { String window = s.substring(i, i+p.length()); windowCount = countChars(window); if( countEqual(pCount, windowCount) == 0) result.add(i); } return result; } }

Performance
Has two input with size M, N, the time complexity is O(MN)
space complexity is O(1)

Although the execution speed is quite slow, it is a good algorithm to elaborate during the interview.