Leet Code 541. Reverse String II

Question

• https://leetcode.com/problems/reverse-string-ii/

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original

文字列sと整数kが与えられたとき、文字列の先頭から数えて2k文字ごとに、最初のk文字を反転させる。

残りの文字数がk文字未満の場合は、すべての文字を反転させる。2k文字未満でk文字以上の場合は、最初のk文字を反転させ、残りは元のままとする。

Code

import kotlin.math.min

class Solution {
    fun reverseStr(s: String, k: Int): String {
        var sm = s.toMutableList()
        for (start in s.indices step 2*k) {
            var left = start
            var right = min(start+k-1, s.length-1)
            while (left < right) {
                val tmp = sm[left]
                sm[left] = sm[right]
                sm[right] = tmp
                left++
                right--
            }
        }
        return sm.joinToString("")
    }
}

ポイントは、

• reverse範囲の左端indexが2k文字ごとに動くのでforのイテレーションで飛ばし飛ばしに位置決めを行う
• reverse範囲の右端indexは左端indexの位置からkだけ右に移動した箇所であるから、start+k-1とすること
• reverseの処理は、左端と右端をそれぞれ中央方向に移動させながらスワップさせること

以下は、s = abcdefg, k=3のときの例

Profile

• Runtime: 388 ms
• Memory Usage: 43.2 MB

Submission

• https://leetcode.com/submissions/detail/592509108/