Anagram Recursion Scala

Question

This is the question that I tried to write a code for.

---

Consider a recursive algorithm that takes two strings s1 and s2 as input and checks if these strings are the anagram of each other, hence if all the letters contained in the former appear in the latter the same number of times, and vice versa (i.e. s2 is a permutation of s1).

Example:

if s1 = ”elevenplustwo” and s2 = ”twelveplusone” the output is true

if s1 = ”amina” and s2 = ”minia” the output is false

Hint: consider the first character c = s1(0) of s1 and the rest of r =s1.substring(1, s1.size) of s1. What are the conditions that s2 must (recursively) satisfy with respect to c and r?

---

And this is the piece of code I wrote to solve this problem. The problem is that the code works perfectly when there is no repetition of characters in the strings. For example, it works just fine for amin and mina. However, when there is repetition, for example, amina and maina, then it does not work properly.

How can I solve this issue?

import scala.collection.mutable.ArrayBuffer

object Q32019 extends App {
def anagram(s1:String, s2:String, indexAr:ArrayBuffer[Int]):ArrayBuffer[Int]={

  if(s1==""){
    return indexAr
  }
  else {
  val c=s1(0)
  val s=s1.substring(1,s1.length)
    val ss=s2
    var count=0
   for (i<-0 to s2.length-1) {
    if(s2(i)==c && !indexAr.contains(s2.indexOf(c))) {
      indexAr+=i
      }
    }

    anagram(s,s2,indexAr)
  }
indexAr
}
  var a="amin"
  var b="mina"
  var c=ArrayBuffer[Int]()
  var d=anagram(a,b,c)
  println(d)
  var check=true
  var i=0
  while (i<a.length && check){
    if (d.contains(i) && a.length==b.length) check=true
    else check=false
    i+=1
  }
  if (check) println("yes they are anagram")
  else println("no, they are not anagram")
}

Answer 1

The easiest way is probably to sort both strings and just compare them:

def areAnagram(str1: String, str2: String): Boolean =
  str1.sorted == str2.sorted

println(areAnagram("amina", "anima")) // true
println(areAnagram("abc", "bcc"))     // false

---

Other one is more "natural". Two strings are anagrams if they have the same count of each character.
So you make two Map[Char, Int] and compare them:

import scala.collection.mutable

def areAnagram(str1: String, str2: String): Boolean = {
  val map1 = mutable.Map.empty[Char, Int].withDefaultValue(0)
  val map2 = mutable.Map.empty[Char, Int].withDefaultValue(0)
  for (c <- str1) map1(c) += 1
  for (c <- str2) map2(c) += 1
  map1 == map2
}

There is also another version of second solution with Arrays probably, if you know the chars are only ASCII ones.
Or some other clever algorithm, IDK.

---

EDIT: One recursive solution could be to remove the first char of str1 from str2. The rests of both strings must be anagrams also.
E.g. for ("amina", "niama") first you throw out an a from both, and you get ("mina", "nima"). Those 2 strings must also be anagrams, by definition.

def areAnagram(str1: String, str2: String): Boolean = {

  if (str1.length != str2.length) false
  else if (str1.isEmpty) true // end recursion
  else {
    val (c, r1) = str1.splitAt(1)
    val r2 = str2.replaceFirst(c, "") // remove c
    areAnagram(r1, r2)
  }
}