Longest Substring Without Repeating Characters in Scala

Question

Question is taken from Leetcode and solution works for their test cases. I do see a scope of improvement and make it more functional (getting rid of vars and mutables data structures). Please suggest improvement to help me.

Problem

Given a string, find the length of the longest substring without repeating characters.

Input: "abcabcbb" Output: 3 Input: "bbbbb" Output: 1 Input: "pwwkew" Output: 3 

code

import scala.collection.mutable.HashMap object Solution extends App{ def lengthOfLongestSubstring(s: String): Int = { if (s.isEmpty) 0 else { val lookupTable = HashMap[Char,Int]() var start = 0 var length = 0 for ( (c, i) <- s.zipWithIndex) { if (!(lookupTable contains c)) { lookupTable(c) = i } else { val newLength = i - start if (newLength > length) length = newLength start = lookupTable(c) + 1 lookupTable.retain((k,v) => v >= start) lookupTable(c) = i } } Math.max(length, (s.length - start)) } } Seq("abcabcbb", "pwwkew", "", "nnnn", "b", " ", "aab" , "abca" ,"abba") foreach { s => println(s + " = " + lengthOfLongestSubstring(s)) } } 

Output

abcabcbb = 3 pwwkew = 3 = 0 nnnn = 1 b = 1 = 1 aab = 2 abca = 3 abba = 2 

Answer 1

Some observations while looking over the code:

1. if (s.isEmpty) 0 - This isn't necessary. The code produces the correct results without this test. Removing it would reduce the level of indenting for the rest of the code.
2. if (!(lookupTable contains c)) - Dijkstra suggests that it is usually better to test for the positive condition, especially when there is an else block. It's often much easier to read and parse that way. In this case the else condition is "NOT table has c == false". (Ouch!)
3. val newLength - You actually don't need this variable. Try:length = length max i - start

4. lookupTable(c) = i - This assignment is made on both sides of the if test, which means it really doesn't belong there.

   if (lookupTable contains c) { length = length max i - start start = lookupTable(c) + 1 lookupTable.retain((k,v) => v >= start) } lookupTable(c) = i 

But, of course, the most noteworthy is the use of mutable variables and data structures. Sometimes we have to fall back on imperative programming if functional means/methods are creating a bottleneck, but, short of that, the point of learning/using Scala is its Functional Programming capability.

Here's a reworking of the same algorithm using two index values to access a static array of characters. Each index is advanced via tail-recursive methods so everything remains immutable.

def lengthOfMaxSubstring(s: String): Int = { val chars: Array[Char] = s.toArray def headForward(leadx: Int, rearx: Int, cSet: Set[Char], best: Int): Int = { def tailForward(tlx: Int, cs: Set[Char]): (Int, Set[Char]) = if (chars(tlx) == chars(leadx)) (tlx + 1, cs) else tailForward(tlx + 1, cs - chars(tlx)) if (leadx >= chars.length) best max leadx-rearx else if (cSet(chars(leadx))) { val (newTail, newSet) = tailForward(rearx, cSet) headForward(leadx+1, newTail, newSet, best max leadx-rearx) } else headForward(leadx+1, rearx, cSet + chars(leadx), best) } headForward(0, 0, Set(), 0) }