763.partition-labels.md

763. Partition Labels

The problem is asking to partition so that all the same characters are in the same partition.

|a .. a .. a| // All 'a' are in the same partition
            |b .. b| // All 'b' are in the same partition

In this case, we have to know the last index of every unique character, and extend the farest index for every character until the current index is equal to the farest index (we reach the index that every characters occur in this partition)

fun partitionLabels(s: String): List<Int> {
    val lastIndex = IntArray(26)
    for (i in 0 until s.length) {
        val c = s[i]
        lastIndex[c - 'a'] = i
    }
    val result = mutableListOf<Int>()
    var farest = 0
    var startIndex = 0
    for (i in 0 until s.length) {
        farest = maxOf(farest, lastIndex[s[i] - 'a'])
        if (farest <= i) {
            result.add(i - startIndex + 1)
            startIndex = i + 1
        }
    }
    return result
}

        0 1 2 3 4 5 6 7 8 9 10
        a b c a d b e f d i j
        a     a
          b       b
            c   
                d       d
            e 
                      f  
                          i 
                            j
index   0 1 2 3 4 5 6 7 8 9 10
farest  3 5 5 5 8 8 8 8 8 9 10
partition               | | |

• Time Complexity: O(n).
• Space Complexity: O(1).