3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Note, I don't think about performance, only about kotlin.

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.
Instead of writing

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 {
    ...
}

function with receiver

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
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Wow, great answer! I learned more about kotlin coding techniques and reduced the redundancy of my function. Thank you :) \$\endgroup\$ – GoldFlsh Feb 10 '20 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.