Checking whether strings are permutations of each other in Swift

Question

I'm solving this problem on Hacker Earth, just for practice. The exercise is to determine whether two given equal-length strings are permutations of each other.

Except for this one test case, which has 100 very long strings to compare, all other test cases are fine. But that one is taking too long to execute. What are possible optimizations that can be done?

Also it would be great if you can tell me what expensive operations I have used.

import Foundation;
var response:String = readLine()!
func createDictionary(from arrayOfCharacters: [Character], _ charCount: Int) -> Dictionary<Character, Int>{
 var dict : [Character: Int] = [:];
 for index in 0...charCount-1{
 if(dict.index(forKey: arrayOfCharacters[index]) != nil){
 dict[arrayOfCharacters[index]] = dict[arrayOfCharacters[index]]!+1;
 }
 else{
 dict[arrayOfCharacters[index]] = 1;
 }
 }
 return dict;
}
func checkEqual(_ x:String) -> Bool{
 var flag = false;
 var names = x.components(separatedBy: " ");
 //let charCount = names[0].characters.count;
 let charCount = (x.characters.count-1)/2;
 var dictionaryOne: [Character:Int] = [:];
 var dictionaryTwo: [Character:Int] = [:];
 if(names[1].characters.count == charCount){
 var charsOfStringOne = Array(names[0].characters);
 var charsOfStringTwo = Array(names[1].characters);
 //print(charsOfStringOne);
 //print(charsOfStringTwo);
 dictionaryOne = createDictionary(from: charsOfStringOne, charCount);
 dictionaryTwo = createDictionary(from: charsOfStringTwo, charCount);
 for char in "abcdefghijklmnopqrstuvwxyz".characters {
 if(dictionaryOne[char] != dictionaryTwo[char]){
 return false;
 }
 }
 if(dictionaryOne != dictionaryTwo){
 return false;
 }else{
 flag=true;
 }
 return flag;
 }else{
 return flag;
 }
}
var debug = false;
var count = Int(response)!
 for _ in 1...count {
 var line = readLine()!;
 if(checkEqual(line)){
 if(debug){
 print(line, "YES")
 }
 else {
 print("YES");
 }
 }else{
 if(debug){
 print(line, "NO")
 }
 else {
 print("NO");
 }
 } 
}

• user1118321: Another method to determine if one is a permutation of the other is to just sort the characters and compare the resulting sorted strings.
• Martin R: @user1118321: Yes, but sorting a string of length N requires O(N*log(N)) operations. The above method is O(N) – assuming that the dictionary operations are O(1).

Answer 1

First some general remarks:

• There is no need to terminate statements with a semicolon in Swift.

• The condition in an if-statement does not require parentheses, e.g.

  if debug { ... }
  

• You should be consistent about whether to start else on a new line or not, I prefer

  if condition {
   // ...
  } else {
   // ...
  }
  

• Many of your variables are not mutated and should be declared as constants, e.g.

  let line = readLine()!
  

---

The overall structure can be improved. Why is the first input line read at the top of the program, and the remaining lines at the bottom? I would do the complete input parsing in the "main" part of the program, which would then look like this:

let numTestCases = Int(readLine()!)!
for _ in 1...numTestCases {
 let strings = readLine()!.components(separatedBy: " ")
 if checkEqual(first: strings[0], second: strings[1]) {
 print("YES")
 } else{
 print("NO")
 }
}

(I have omitted the "debug" feature for simplicity.)

---

About the createDictionary() function: A loop like

for index in 0...charCount-1 {
 // ... do something with `arrayOfCharacters[index]` ...
}

can always be simplified using enumeration:

for char in arrayOfCharacters {
 // ... do something with `char` ...
}

But actually you don't have to create an array with all characters at all: You can pass the string itself to the function, and enumerate its characters:

func createDictionary(from string: String) -> [Character:Int] {
 var dict = ...
 for char in string.characters {
 // insert or update `dict[char]` ...
 }
 return dict
}

The nil-coalescing operator ?? can be used to simplify the "insert or update". Also it might be advantageous to create the dictionary with the required capacity, in order to avoid rehashing.

The function would then look like this:

func createDictionary(from string: String) -> [Character:Int] {
 var dict: [Character: Int] = Dictionary(minimumCapacity: 26)
 for char in string.characters {
 dict[char] = (dict[char] ?? 0) + 1
 }
 return dict
}

---

About the func checkEqual() function:

• A better name might be checkPermutation().
• The var flag is not really needed because you always "early return" if the comparison fails.
• There is no need to assign empty dictionaries to var dictionaryOne/Two first because they are overwritten later.

• You also don't have to compare the strings lengths because they are always equal according to the problem statement.

• The

  for char in "abcdefghijklmnopqrstuvwxyz".characters { ... }
  

  loop is superfluous, it suffices to compare the dictionaries

  if dictionaryOne != dictionaryTwo { ... }
  

Putting it all together, that function reduces to

func checkPermutation(first: String, second: String) -> Bool {
 let dictionaryOne = createDictionary(from: first)
 let dictionaryTwo = createDictionary(from: second)
 return dictionaryOne == dictionaryTwo
}

---

Some syntactic sugar: If you replace the global function by an extension method of String:

extension String {
 func isPermutation(of other: String) -> Bool {
 // ...
 }
}

then the check can be more expressively done as

if strings[0].isPermutation(of: strings[1]) { ... }

---

For further performance improvement, note that the strings consist of lowercase letters only, i.e. there are only 26 possible characters. Therefore you can use a fixed-size array instead to count the number of occurrences of each letter in the strings. Array subscripting is much faster than dictionary lookups.

In order to compute a number (from 0 to 25) from each lowercase letter, it is more convenient to enumerate the unicodeScalars of the string. This leads to the following implementation:

extension String {
 func characterCounts() -> [Int] {
 let letterA: UnicodeScalar = "a"
 var counts = Array(repeating: 0, count: 26)
 for ucs in self.unicodeScalars {
 let offset = ucs.value - letterA.value
 assert(offset >= 0 && offset < 26, "only lowercase letter 'a'...'z' allowed")
 counts[Int(offset)] += 1
 }
 return counts
 }
 func isPermutation(of other: String) -> Bool {
 let counts1 = self.characterCounts()
 let counts2 = other.characterCounts()
 return counts1 == counts2
 }
}
let numTestCases = Int(readLine()!)!
for _ in 1...numTestCases {
 let strings = readLine()!.components(separatedBy: " ")
 if strings[0].isPermutation(of: strings[1]) {
 print("YES")
 } else{
 print("NO")
 }
}