Skip to content

2337.move-pieces-to-obtain-a-string.md

Latest commit

 

History

History
279 lines (230 loc) · 7.97 KB

2337.move-pieces-to-obtain-a-string.md

File metadata and controls

279 lines (230 loc) · 7.97 KB

2337. Move Pieces to Obtain a String

Hints

  • What happens if you ignore the blanks (_) and just look at the order of L and R?
  • For each L and R, can you always move them to their target positions? What are the constraints?
  • Try to match each piece in start with the corresponding piece in target.

Breakdowns

  1. Can we ignore the blanks and just compare the order of L and R?

If the order of L and R is not the same in both strings, it's impossible to transform.

  1. For each L and R, what are the movement constraints?
  • L can only move left (to a lower index).
  • R can only move right (to a higher index).

Key Insights

The relative order of L and R must be the same. We can ignore the blank _ and compare the characters, if the sequences of L and R are not the same order, such as LR and RL, it is invalid.

We track the index position of L and R in each string, and compare the relative position of L and R in both strings: For each L: It can only move to the left, so it allows to have more space in start than target.

  • In start, index = i
  • In target, index = j

It valid only if i >= j, invalid the position in start is less than the position in target.

// Valid
start =  _, _, _, L
target = _, _, L

// Valid
start =  _, _ L
target = _, _ L

// Invalid
start =  _, _, L
target = _, _, _, L

For each R: It can only move to the right, so it allows to have less space in start than target.

  • In start, index = i
  • In target, index = j

It valid only if i <= j, invalid the position in start is greater than the position in target.

// Valid
start =  R, ...
target = _, R, ...

start =  R, ...
target = R, ...

// Invalid
start =  _, R, ...
target = R, ...

Two Pointers

private val blank = '_'

fun canChange(start: String, target: String): Boolean {
    // Check the sequence of `L` and `R` is the same
    if (start.filter { it != blank } != target.filter{ it != blank }) return false

    val sL = mutableListOf<Int>()
    val sR = mutableListOf<Int>()
    val tL = mutableListOf<Int>()
    val tR = mutableListOf<Int>()
    val n = start.length

    for (i in 0 until n) {
        val s = start[i]
        val t = target[i]
        if (s == 'L') sL.add(i)
        if (s == 'R') sR.add(i)
        if (t == 'L') tL.add(i)
        if (t == 'R') tR.add(i)
    }

    for (i in sL.indices) {
        if (sL[i] < tL[i]) return false
    }   

    for (i in sR.indices) {
        if (sR[i] > tR[i]) return false
    }
    return true
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Two Pointers (Space Optimized)

The key idea is the same as the previous solution, but we use two pointers to scan both strings, skipping blanks, and check the movement constraints for each L and R.

private val blank = '_'

fun canChange(start: String, target: String): Boolean {
    val n = start.length
    var s = 0
    var t = 0
    /**
     * We use OR rather than AND because we continue processing
     * until both strings are fully processed.
     * 
     * Ex:
     * s = "_L"
     * t = "LR" See below.
     */
    while (s < n || t < n) {
        // Move to the first non-blank characters
        while (s < n && start[s] == blank) s++
        while (t < n && target[t] == blank) t++

        // If one of the pointer reaches the end, check if both pointers have reached the end
        if (s == n || t == n) {
            return s == n && t == n
        }
        // The character should be the same now
        if (start[s] != target[t]) return false

        // Check the relative position of `L` and `R`
        if (start[s] == 'L' && s < t) return false
        if (start[s] == 'R' && s > t) return false

        s++
        t++
    }
    return true
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Why use OR while (s < n || t < n)?

If we use AND while (s < n && t < n), we will stop processing when one of the strings is fully processed. For example: s = '_L' and t = 'LR', it doesn't detect that t stil have R left while s reaches the end.

Correct implementation: while (s < n || t < n).

start = "_L"
target = "LR"

s = 0, t = 0

// skip '_' in start
start[0] == '_' → s = 1
target[0] == 'L' → no skip → t = 0

// now s = 1, t = 0
start[1] = 'L', target[0] = 'L' ✅ match

// Now check if L can move from s=1 → t=0
// Rule: L can only move left → ✅ s >= t → 1 >= 0 → OK

s++, t++ → s = 2, t = 1

// Now s == 2 (out of bound), but t == 1 → keep going

target[1] = 'R' → not blank → proceed

Now s = 2 (exhausted), but t = 1 ('R' remaining)

⚠️ `s == n`, `t < n` → ❌ return false

Edge Cases

  • All blanks: Both strings are all _, should return true.
  • Only L or only R: Make sure the movement direction is respected.
  • start and target have different non-blank sequences: Should return false.
  • L or R in the wrong direction: e.g., L, _, _ needs to move right, or _, _, R needs to move left.

Pitfalls

  • Forgetting to check the order of L and R after removing blanks.
  • Not handling the case where one pointer reaches the end before the other.
  • Allowing L to move right or R to move left (should be invalid).
  • Not checking for extra non-blank characters at the end of either string.

Similar or Follow-up Problems

WA

The main issues with the implementation are:

  1. The logic for handling spaces and movement constraints is overly complicated and error-prone.
  2. The implementation has several bugs:
    • Using sSize instead of tSize in one of the while loop conditions
    • The space counting logic is confusing and doesn't correctly handle the movement constraints
    • The break condition when reaching the end of strings is incorrect
    • The logic for handling 'R' characters is incomplete
private val blank = '_'
fun canChange(start: String, target: String): Boolean {
    if (isSamePattern(start, target).not()) return false

    val sSize = start.length
    var tSize = target.length
    var s = 0
    var t = 0
    var space = 0
    while (s < sSize && t < tSize) {
        // Move to the first non-blank characters
        var sSpace = 0
        var tSpace = 0
        while (s < sSize && start[s] == blank) {
            sSpace++
            s++
        }
        while (t < tSize && target[t] == blank) {
            tSpace++
            t++
        }
        if (s == sSize || t == sSize) break

        if (start[s] == 'L') {
            space += sSpace - tSpace
            /**
            invalid
            _, L
            _, _, L
            */
            if (space < 0) return false
            s++
            t++
        } else if (start[s] == 'R') {
            /**
            invalid
            _, _, R
            _, R
                */
            if (sSpace > tSpace) return false
            else if (sSpace == tSpace) { // valid, move to next character
                s++
                t++
                continue
            }
            
            // Collect blank between current and next character
            space = 0
            s++
            t++
            sSpace = 0
            tSpace = 0
            while (s < sSize && start[s] == blank) {
                sSpace++
                s++
            }
            while (t < tSize && target[t] == blank) {
                tSpace++
                t++
            }
            space += sSpace - tSpace
            if (space < 0) return false
        }
    }
    return true
}

private fun isSamePattern(start: String, target: String): Boolean {
    val s = mutableListOf<Char>()
    val t = mutableListOf<Char>()
    for (c in start) {
        if (c != blank) s.add(c)
    }
    for (c in target) {
        if (c != blank) t.add(c)
    }
    if (s.size != t.size) return false
    for (i in s.indices) {
        if (s[i] != t[i]) return false
    }
    return true
}