Scala program to find the longest substring without repeating characters

1. Introduction

Finding the longest substring without repeating characters from a given string is a common problem in programming, often used in coding interviews and string manipulation tasks. In this post, we will walk through a Scala solution to address this problem.

2. Program Steps

1. Set up the Scala environment.

2. Create an object to house the main function.

3. Define a method that will iterate through the given string and maintain a sliding window to track the longest substring without any repeating characters.

4. Handle corner cases where the string is empty or consists of a single character.

5. Invoke the method and display the result.

6. Execute the program.

3. Code Program

object LongestSubstringApp {
  def main(args: Array[String]): Unit = {
    val str = "abcabcbb"
    val longestSubstring = findLongestSubstring(str)
    println(s"Original String: $str")
    println(s"Longest Substring without Repeating Characters: $longestSubstring")
  }

  def findLongestSubstring(s: String): String = {
    var start = 0
    var maxLength = 0
    var maxStart = 0
    val seen = scala.collection.mutable.Map[Char, Int]()

    for (end <- s.indices) {
      if (seen.contains(s(end))) {
        start = math.max(start, seen(s(end)) + 1)
      }
      if (end - start + 1 > maxLength) {
        maxLength = end - start + 1
        maxStart = start
      }
      seen(s(end)) = end
    }

    s.substring(maxStart, maxStart + maxLength)
  }
}

Output:

Original String: abcabcbb
Longest Substring without Repeating Characters: abc

Explanation:

1. The program begins with an object named LongestSubstringApp, housing the main function.

2. Inside the main function, we have the input string str for which we aim to find the longest substring without repeating characters.

3. The function findLongestSubstring is tasked with finding this substring. It utilizes the sliding window approach, which is a common method for such problems. As we move through each character in the string, we maintain the beginning (start) of the current substring and use a map (seen) to keep track of characters and their most recent indices.

4. If a character is repeated, we adjust the start position to the position after the previously seen occurrence of that character. This helps ensure that our current substring has no repeating characters.

5. We track the maximum length found (maxLength) and the starting index of this substring (maxStart).

6. Finally, the method returns the longest substring using the substring method on the original string with the maxStart and maxLength values.