# Longest Substring without Repeating Characters Problem - Kotlin Recursion

I am practicing coding questions on leetcode. I have been an OOP my whole career, and I am trying to wade into the dark abyss that is functional programming. So I am trying to do things purely functional, e.g. using recursion to try to get to the answer. The problem statement is this: Given a string, find the length of the longest substring without repeating characters.

Sorry for asking literally this leetcode question that everybody else is asking :D

I have coded up this solution -

class Solution {
fun lengthOfLongestSubstring(str: String): Int {
return when {
str.length == 1 -> 1
str.isEmpty() -> 0
else -> helper(str, 0, 1, 0)
}
}

private tailrec fun helper(str: String, leftIndex: Int, rightIndex: Int, max: Int): Int {
return when {
rightIndex >= str.length+1 -> max
rightIndex >= str.length && isDistinct(str.substring(leftIndex)) ->
helper(str, leftIndex, rightIndex + 1, max(rightIndex - leftIndex, max))
isDistinct(str.substring(leftIndex, rightIndex)) ->
helper(str, leftIndex, rightIndex + 1, max(rightIndex - leftIndex, max))
else -> helper(str, leftIndex + 1, leftIndex + max + 1, max)
}
}

private fun isDistinct(substring: String): Boolean {
return substring.toList().distinct().size == substring.length
}
}


I have a couple specific questions - I am using the sliding window approach, is that appropriate in a functional setting? If not, what is a better approach functionally, speaking.

Is there redundancy in my recursion function that I can get rid of?

What things can I do to improve the legibility of the function? Clean code is always best!

What further steps can I take to optimize the solution? Currently this solution is only faster than 10% of other solutions (though those are likely imperative solutions)

Any other tips you can provide outside of the bounds of my question that can help would be awesome. I am also brand new to kotlin programming.

I don't necessarily hate this solution, but I'm sure it can be better. Please advise.

# Iluminate branch

in your when, you check if the rightIndex >= string.length+1.
this means in the next branches the size is maximal string.length. Substring is exclusive, so it allows str.length.
this means the second and third branches are identical.

# Use Set

It would make more sense to me to use toSet instead of toList.distinct, because sets are meant to hold distinct versions.

# personal Choices:

### Single-expression function

A single-expression-function is a function with one expression 🙄.
In kotlin, you can write this in an easier way.

fun lengthOfLongestSubstring(str: String): Int {
return when {
...
}
}


you can write

fun lengthOfLongestSubstring2(str: String): Int = when {
...
}


or even without return-type:

fun lengthOfLongestSubstring2(str: String) = when {
...
}


I personally like to write these like:

fun helper(
str: String,
leftIndex : Int,
rightIndex : Int,
max: Int
) = when {
...
}


If I'm right functional means:

• The function knows about the type and the type doesn't know about the function
• If a function receives the same input, it should return the same output

(or only the later)

The first way is often expressed by having a function that only takes parameters, but is not called on an object: b(a) instead of a.b()

Kotlin allows to let a function like b(a) look like a.b(), if you define it that way. This is called a function with receiver.
Note, inside de function-body, you refer to the receiver using this.

isDistinct("hi")
private fun isDistinct(
substring: String
): Boolean = substring.toSet().size == substring.length


can be rewritten to

"hi".isDistinct()
private fun String.isDistinct() : Boolean = this.toSet().size == this.length


And as you don't have to call this inside a scope:

"hi".isDistinct()
private fun String.isDistinct() : Boolean = toSet().size == length


Or just:

"hi".isDistinct()
private fun String.isDistinct() = toSet().size == length


Under the scenes it's still the same function. Inside kotlin, you can't call it the old way anymore

# New code

class Solution {
fun lengthOfLongestSubstring(
str: String
) = when {
str.length == 1 -> 1
str.isEmpty() -> 0
else -> helper(str, 0, 1, 0)
}

private tailrec fun helper(
str: String,
leftIndex: Int,
rightIndex: Int,
max: Int
): Int = when {
rightIndex >= str.length + 1 -> max
str.substring(leftIndex, rightIndex).isDistinct() ->
helper(str, leftIndex, rightIndex + 1, max(rightIndex - leftIndex, max))
else -> helper(str, leftIndex + 1, leftIndex + max + 1, max)
}

private fun String.isDistinct() = toSet().size == length
}

• Wow, great answer! I learned more about kotlin coding techniques and reduced the redundancy of my function. Thank you :) Feb 10 '20 at 14:34