11 March 2015
Problem overview
Given two strings (of same or different length) design an algorithm to find the minimum number of character deletions required to make two strings anagrams. Any character can be deleted from any of the strings.
Two strings are anagrams of each other if they have same character set. For example strings "delight" and "ldihgte" are anagrams, while strings "abcde" and "abcdf" are not.
Algorithm analysis
Count character occurences on each string, and subtract the difference for each found character until value is the same.
Code in Java
Below is the code that depicts the idea above:
public static int getNumCharsDeleteToMakeAnagram(String s1, String s2) {
if (s1 == null || s2 == null || s1.equals("") || s2.equals("")) {
return -1;
}
<span class="n">s1</span> <span class="o">=</span> <span class="n">s1</span><span class="o">.</span><span class="na">toLowerCase</span><span class="o">();</span>
<span class="n">s2</span> <span class="o">=</span> <span class="n">s2</span><span class="o">.</span><span class="na">toLowerCase</span><span class="o">();</span>
<span class="k">if</span> <span class="o">(</span><span class="n">s1</span><span class="o">.</span><span class="na">equals</span><span class="o">(</span><span class="n">s2</span><span class="o">))</span> <span class="o">{</span>
<span class="k">return</span> <span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>
<span class="kt">int</span><span class="o">[]</span> <span class="n">charCountS1</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="mi">26</span><span class="o">];</span>
<span class="kt">int</span><span class="o">[]</span> <span class="n">charCountS2</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="mi">26</span><span class="o">];</span>
<span class="kt">int</span> <span class="n">indexOfChar</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
<span class="kt">char</span><span class="o">[]</span> <span class="n">sc1</span> <span class="o">=</span> <span class="n">s1</span><span class="o">.</span><span class="na">toCharArray</span><span class="o">();</span>
<span class="kt">char</span><span class="o">[]</span> <span class="n">sc2</span> <span class="o">=</span> <span class="n">s2</span><span class="o">.</span><span class="na">toCharArray</span><span class="o">();</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">sc1</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">indexOfChar</span> <span class="o">=</span> <span class="n">sc1</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">-</span> <span class="sc">'a'</span><span class="o">;</span>
<span class="n">charCountS1</span><span class="o">[</span><span class="n">indexOfChar</span><span class="o">]++;</span>
<span class="o">}</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">sc2</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">indexOfChar</span> <span class="o">=</span> <span class="n">sc2</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">-</span> <span class="sc">'a'</span><span class="o">;</span>
<span class="n">charCountS2</span><span class="o">[</span><span class="n">indexOfChar</span><span class="o">]++;</span>
<span class="o">}</span>
<span class="kt">int</span> <span class="n">numChars</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">charCountS1</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="k">if</span> <span class="o">(</span><span class="n">charCountS1</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">!=</span> <span class="n">charCountS2</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
<span class="k">while</span> <span class="o">(</span><span class="n">charCountS1</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">></span> <span class="n">charCountS2</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
<span class="n">charCountS1</span><span class="o">[</span><span class="n">i</span><span class="o">]--;</span>
<span class="n">numChars</span><span class="o">++;</span>
<span class="o">}</span>
<span class="k">while</span> <span class="o">(</span><span class="n">charCountS1</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o"><</span> <span class="n">charCountS2</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
<span class="n">charCountS2</span><span class="o">[</span><span class="n">i</span><span class="o">]--;</span>
<span class="n">numChars</span><span class="o">++;</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">numChars</span><span class="o">;</span>
}