Here's an implementation of finding the longest substring that does not contain any repeating characters in Scala:
def longestSubstring(s: String): String = {
var start = 0
var end = 0
var maxLength = 0
var substrStart = 0
var charMap = Map[Char, Int]()
for (i <- 0 until s.length) {
val c = s(i)
if (charMap.contains(c) && charMap(c) >= start) {
start = charMap(c) + 1
}
charMap += (c -> i)
end = i
if (end - start + 1 > maxLength) {
maxLength = end - start + 1
substrStart = start
}
}
s.substring(substrStart, substrStart + maxLength)
}
The main algorithm is based on the sliding window technique, where we maintain a "window" of unique characters as we scan the input string from left to right. We use a mapping from characters to their indices in the string to keep track of the last occurrence of each character in the window. When we encounter a repeated character, we move the starting point of the window to the index after the last occurrence of that character.
We also keep track of the starting index and length of the longest substring seen so far. When the window is updated, we compare the length of the current window to the longest seen so far, and update the longest substring if necessary.
Finally, we return the longest substring by using the substring method on the original input string based on the starting index and length of the longest substring.
Please start posting anonymously - your entry will be published after you log in or create a new account. This space is reserved only for answers. If you would like to engage in a discussion, please instead post a comment under the question or an answer that you would like to discuss
Asked: 2022-04-05 11:00:00 +0000
Seen: 8 times
Last updated: Aug 09 '22
In SCSS, what is the method for grouping and reusing a set of classes and styles?
What is the method to distinguish the presence of a json field in an array using presto?
What is Nextflow for genomics in AWS?
What does "waiting for handler commit" mean in relation to the slow writes experienced in MySQL 8?
What is the best way to arrange the file structure for both the backend and frontend in MERN?
What are the differences between EJS/Handlebars and Nextjs?
How can a Python function (REFPROP 9.1) be turned into a vectorized version?