k-anagrams

README.md

Given two strings of lowercase alphabets and a value k, the task is to find if two strings are K-anagrams of each other or not.

Two strings are K-anagrams of each other if they can become anagram by replacing at most k characters in a string.

Implement a function isKAnagram that returns true if the two strings are k-anagram, or false if they are not.

solution.hs

import Data.Map.Strict as M
import Data.Monoid

isKAnagram :: String -> String -> Int -> Bool
isKAnagram a b k = maybe False (<= k) $ replacements a b

replacements :: String -> String -> Maybe Int
replacements a b =
  case diffs a b of
    Just d -> 
      let Sum count = foldMap (Sum . abs) d
          (q, r) = quotRem count 2
      in if r == 0 then Just q else Nothing
    Nothing -> Nothing

diffs :: String -> String -> Maybe (Map Char Int)
diffs a b = go a b M.empty
  where
    go (a:as) (b:bs) acc = go as bs $ M.insertWith (+) a 1 $ M.insertWith (+) b (-1) $ acc
    go [] [] acc = Just acc
    go _ _ _ = Nothing

solution.scala

import scala.collection.immutable.HashMap

object Solution extends App {
  val cases = List(("anagram", "grammar", 2),
                   ("geeks", "eggkf", 1))
  
  for ((a,b,k) <- cases) {
     println((a,b))
     println(diffs(a,b))
     println(replacements(a,b))
     println(isKAnagram(a,b,k))
  }

  def isKAnagram(a: String, b: String, k: Int): Boolean =
    replacements(a, b).fold(false)(_ <= k)

  def replacements(a: String, b: String): Option[Int] =
    diffs(a,b).map(_.values.fold(0)((x,y) => x.abs + y.abs) / 2)

  def diffs(a: String, b: String): Option[HashMap[Char, Int]] = {
    def go(a: String, b: String, acc: HashMap[Char, Int]): Option[HashMap[Char, Int]] = {
      def update(neu: Int)(old: Option[Int]): Option[Int] =
        old.fold(Some(neu))(o => Some(o+neu))

      a.splitAt(1) -> b.splitAt(1) match {
        case ((a,_), (b,_)) if a.isEmpty && !b.isEmpty => None
        case ((a,_), (b,_)) if b.isEmpty && !a.isEmpty => None
        case ((a,_), (b,_)) if a.isEmpty && b.isEmpty => Some(acc)
        case ((a,as), (b,bs)) =>
          go(as, bs, acc
            .updatedWith(a.head)(update(1))
            .updatedWith(b.head)(update(-1)))
      }
    }

    go(a, b, HashMap.empty)
  }
}

solutionEarlyTermination.hs

import Data.IntMap.Lazy as M
import Data.Char

import Data.Monoid
import Control.Monad
import Control.Exception

main = do
  forM_ [ ("ab", "a", 1, False)
             , ("ab", "ab", 0, True)
             , ("ab", "ab", 1, True)
             , ("ab", "ac", 1, True)
             , ("ab", "ac", 0, False)
             , ("ab", "cd", 2, True)
             ] $ \(a,b,k,yesNo) -> do
    print (a,b,k, assert (isKAnagram a b k == yesNo) (unmatchedCount a b))
  -- demonstration of early termination if >k
  print $ checkExceeds 0 $ M.fromList [(0 ,1), (1,undefined)]
  print $ checkExceeds 0 $ M.fromList [(0,-1), (1,undefined)]

isKAnagram :: String -> String -> Int -> Bool
isKAnagram a b k = maybe False (checkExceeds k) $ unmatchedCount a b

checkExceeds :: Int -> IntMap Int -> Bool
checkExceeds k =
     all (\(quota,quota') -> quota >= 0 && quota' <= 0)
   . scanl count (k,-k)
   . elems -- list fusion happens
  where
    count (quota,quota') x | x > 0 = (quota - x, quota')
    count (quota,quota') x | x < 0 = (quota    , quota' - x)
    count acc                _     = acc

unmatchedCount :: String -> String -> Maybe (IntMap Int)
unmatchedCount a b = go a b M.empty
  where
    go (a:as) (b:bs) acc = go as bs
      $ M.insertWith (+) (ord a) 1
      $ M.insertWith (+) (ord b) (-1)
      $ acc
    go [] [] acc = Just acc
    go _ _ _ = Nothing

solutionHeadOption.scala

import scala.collection.immutable.HashMap

object Solution extends App {
  val cases = List(("anagram", "grammar", 2),
                   ("geeks", "eggkf", 1))
  
  for ((a,b,k) <- cases) {
     println((a,b))
     println(diffs(a,b))
     println(replacements(a,b))
     println(isKAanagram(a,b,k))
  }

  def isKAanagram(a: String, b: String, k: Int): Boolean =
    replacements(a, b).fold(false)(_ <= k)

  def replacements(a: String, b: String): Option[Int] =
    diffs(a,b).map(_.values.fold(0)((x,y) => x.abs + y.abs) / 2)

  def diffs(a: String, b: String): Option[HashMap[Char, Int]] = {
    def go(a: String, b: String, acc: HashMap[Char, Int]): Option[HashMap[Char, Int]] = {
      if (a.isEmpty && !b.isEmpty) return None
      if (b.isEmpty && !a.isEmpty) return None
      if (a.isEmpty && b.isEmpty) return Some(acc)

      def update(neu: Int)(old: Option[Int]): Option[Int] =
        old.fold(Some(neu))(o => Some(o+neu))
      
      for {
          x <- a.headOption
          y <- b. headOption
          rest <- go(a.tail, b.tail, acc)
      } yield acc.updatedWith(x)(update(1)).updatedWith(y)(update(-1)) ++ rest
    }

    go(a, b, HashMap.empty)
  }
}