CtCI - Making Anagrams

Alice is taking a cryptography class and finding anagrams to be very useful. We consider two strings to be anagrams of each other if the first string's letters can be rearranged to form the second string. In other words, both strings must contain the same exact letters in the same exact frequency For example, bacdc and dcbac are anagrams, but bacdc and dcbad are not.

Alice decides on an encryption scheme involving two large strings where encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. Can you help her find this number?

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.

// Input
abmno
ghmnoxy

// Output
6

The anagram of two strings is basically the intersection of their characters, in this exercise we will need to extract the intersection, count how many characters can make an anagram out of that intersection, and then subtract that number from the size of each string, this will give us the number of character deletions per input, and summing them up we get the solution.

First of all, we are assuming that both strings are alphabetically ordered, otherwise we have to order them before the execution of the code that will find the intersecting characters. Once both strings are ordered we will start comparing the value of each index in the first string with the values in the second string.

If the value in a[i] < b[j] then we discard the character from a[i] because it clearly is not in the second string, then we increment i++ and continue with the next iteration. If a[i] > b[j] then we discard b[j] because it is not a character inside the first string, then we increment j++ and continue with the next iteration. If a[i] == b[j] then we consider this an intersection and include the character in a bucket, or simply increment both i++ and j++ in case we are counting just the differences.

for {
    if a[i] < b[j] {
        i++
    } else if a[i] > b[j] {
        j++
    } else if a[i] == b[j] {
        count++
        i++
        j++
    }
}

The limit in this case will be the lowest list, this way we can quickly discard the remaining elements of the biggest list by assumption that these characters are not present in the smallest list. Here is a step-by-step representation of how this iteration works.

  1. Initialize the number of intersections as C=0,
  2. Consider A as a list of characters [a, b, m, n, o],
  3. Consider B as a list of characters [g, h, m, n, o, x, y],
  4. Each character will be checked so we initialize i=0 and j=0,
  5. We start an iteration from zero the number of elements in the smallest list,
  6. A[i=0] < B[j=0] because character a is lower than character g, in this case we will discard character a, and move its index one digit forward so we can check the next character in A, so we do i++ and leave j as it is,
  7. A[i=1] < B[j=0] because character b is lower than character g, in this case we will discard character b, and move its index one digit forward so we can check the next character in A, so we do i++ and leave j as it is,
  8. A[i=2] > B[j=0] because character m is greater than character g, in this case we will discard character g, and move its index one digit forward so we can check the next character in B, so we do j++ and leave i as it is,
  9. A[i=2] > B[j=1] because character m is greater than character h, in this case we will discard character h, and move its index one digit forward so we can check the next character in B, so we do j++ and leave i as it is,
  10. A[i=2] == B[j=2] because character m is equal to character m, in this case we will not discard anything, but will increase C++ and the indexes for both A and B to continue checking the next characters in both lists, so i++ and j++,
  11. A[i=3] == B[j=3] because character n is equal to character n, in this case we will not discard anything, but will increase C++ and the indexes for both A and B to continue checking the next characters in both lists, so i++ and j++,
  12. A[i=4] == B[j=4] because character o is equal to character o, in this case we will not discard anything, but will increase C++ and the indexes for both A and B to continue checking the next characters in both lists, so i++ and j++,
  13. At this point index i=5 is out of range for list A so break the iteration, this is because A is the smallest of the two strings. Same thing would happen if B was the smallest one, so we will include an statement before all the conditions to check if i > size(A) or j > size(B),
  14. We will end the operation returning the sum of the size of both strings minus the number of intersections, this will give us the number of characters from A and B that are not useful to make an anagram.
func solution(a []byte, b []byte) int {
    var asize int = len(a)
    var bsize int = len(b)
    var count int
    var i int
    var j int

    for {
        /* Prevent index out of range */
        if i >= asize || i >= bsize {
            break
        }

        if a[i] < b[j] {
            i++ /* Delete character A[i] if not in B */
        } else if a[i] > b[j] {
            j++ /* Delete character B[j] if not in A */
        } else if a[i] == b[j] {
            count++ /* Count intersection */
            i++ /* Continue with next character in A */
            j++ /* Continue with next character in B */
        }
    }

    /* Delete intersections from both A and B */
    return (asize - count) + (bsize - count)
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!