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

• ELinda: This solution may be helpful: stackoverflow.com/questions/75905705/…

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)
}