Count number of changes (manipulations) needed to make an anagram in immutable/pure functional Scala with foldLeft and a MultiSet

Problem

Count number of changes needed to make. This problem is similar to:

• On HackerRank: You must split it [a string] into two contiguous substrings, then determine the minimum number of characters to change to make the two substrings into anagrams of one another.

One string is an anagram of another if they have the same number of each character, not necessarily in the same order - for example abcc is an anagram of accb and vice-versa.

ab is composed of a and b, and exchanging a to b is enough to create an anagram - ie 1 change of letter is enough.

abc is not possible to create anagrams of because it cannot be split.

poeq requires 2 changes, to create an anagram, for example to pqpq, popo, eoeo and so forth.

Solution

Test cases

assert(anagramChanges("aaabbb") == Some(3))
assert(anagramChanges("ab") == Some(1))
assert(anagramChanges("mnop") == Some(2))
assert(anagramChanges("xyyx") == Some(0))
assert(anagramChanges("xaxbbbxx") == Some(1))
assert(anagramChanges("abc") == None)

Scala Concepts

Collect

'collect' allows you to use Pattern Matching, to filter and map items.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

assert(
  (1 to 10)
    .map { num =>
      if (num % 3 == 0) Some("Fizz")
      else if (num % 5 == 0) Some("Buzz")
      else None
    }
    .flatten
    .toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz")
)

Collect can be used on any collection, including Streaming collections like LazyList

foldLeft and foldRight

A 'fold' allows you to perform the equivalent of a for-loop, but with a lot less code.

def foldMutable[I, O](
    initialState: O
)(items: List[I])(f: (O, I) => O): O = {
  var result: O = initialState
  items.foreach { item => result = f(result, item) }
  result
}

Becomes:

def foldMutable[I, O](initialState: O)(items: List[I])(f: (O, I) => O): O =
  items.foldLeft(initialState)(f)

So you can see how ta Scala solution that is immutable can be represented in a mutable form. Reverse is also possible.

The big difference is that to the user it is immutable, because you only specify the next value by adding an item to an accumulator.

This presents many possibilities, most important of which is to be able to develop code in a highly predictable and obvious manner, whereas in standard for-loops, many complications can arise (wrong indices, unexpected mutations).

def getUniqueCharacters(string: String): Set[Char] = {
  var setOfCharacters = Set.empty[Char]
  string.foreach { character =>
    setOfCharacters = setOfCharacters + character
  }
  setOfCharacters
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

And in an immutable fashion:

def getUniqueCharacters(string: String): Set[Char] = {
  string.foldLeft(Set.empty[Char])(_ + _)
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

The rule of thumb is: if you want a single result, use `foldLeft`, if you want a set of intermediate results, use scanLeft and scanRight.

Option Type

The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!

Some examples:

final case class Page(title: String, mainCategory: Option[String])

val pages = List(
  Page(title = "Tail Recursion", mainCategory = None /** No category **/ ),
  Page(title = "Option", mainCategory = Some("standard library")),
  Page(title = "zip", mainCategory = Some("standard library"))
)

val categories: Set[String] = pages.flatMap(_.mainCategory).toSet

assert(categories == Set("standard library"))

def pageCategory(title: String): Option[String] = {
  for {
    page <- pages.find(_.title == title)
    category <- page.mainCategory
  } yield category
}

def pageCategory2(title: String): Option[String] =
  pages.find(_.title == title).flatMap(_.mainCategory)

def pageCategory3(title: String): Option[String] =
  pages.collectFirst {
    case Page(`title`, mainCategory) => mainCategory
  }.flatten

assert(pageCategory("zip").contains("standard library"))

assert(pageCategory("zip") == Some("standard library"))

assert(pageCategory("zip") == Some("standard library"))

assert(pageCategory2("zip") == pageCategory("zip"))

assert(pageCategory3("zip") == pageCategory("zip"))

assert(List[String]("X").headOption == Some("X"))

assert(List[String]().headOption.isEmpty)

val startWithT: String = Option("Some test") match {
  case Some(value) if value.startsWith("T") => value
  case Some(value)                          => s"T${value}"
  case None                                 => "T"
}

assert(startWithT == "TSome test")

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

In the example below, we can see the view in action:

var counted = 0

val resultingList = List(1, 2, 3, 4).view
  .map { num =>
    counted = counted + 1
    num + 1
  }
  .take(2)
  .toList

assert(resultingList == List(2, 3))

assert(counted == 2)

If we add a side-effect inside a map (don't do this normally!), We note that items 3 and 4 are never touched/evaluated, meaning we perform a "lazy" computation.

This is very similar to an Iterator, except views can be Indexed, and also reversed, which is a tremendously useful fact when dealing with arrays, for example when you want to zip two arrays together, such as in CheckArrayIsAPalindrome

On views, you can perform almost any typical collection operation, such as `maxBy`, `count`, `flatMap` and so forth.

And you can get views from almost any data type. Benefits other than lazy computation include potentially fusing of operations by the Java compiler, because instead of creating a new list for every stage, you evaluate new items one-by-one, meaning that if there are any optimisations to be made per one-item basis, you may get a performance boost.

Explanation

Once we split a string into 2 parts, we are left with 2 strings. Number of changes required is effectively the number of characters that are not in common.

If we're counting a "difference" between two "sets", then we need a set differentiation operation. But this set is of a particular type - we have counters, so in fact it is a Map-like type. There is a name for it and it is a MultiSet (I discovered this while working out a solution for this problem).

Once we've figured out this aspect, the problem boils down to find the diff between these two sets, which is a generic solution independent of String.

This gives us the count for each character that requires replacing on both sides - we sum this count and divide by 2 eliminate the duplicates.