Posts tagged as “javascript”

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

• S will have length in range [1, 500].
• S will consist of lowercase English letters ('a' to 'z') only.

Idea:

• Create hash table to track the last index of the letter
• use start and end variable to decide the partition letters
• when end reach to the last index of the letter :
  • store the length of the partition letters (end – start + 1)
  • reset start => end + 1

Solution:

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let last_index = new Map();
    for (let i = 0; i < S.length; i++) {
        last_index.set(S[i],  i);
    }
    let res = [];
    let start = 0;
    let end = 0;
    for (let i = 0; i < S.length; i++) {
        end = Math.max(end, last_index.get(S[i]));
        if (i === end) {
            res.push(end - start + 1);
            start = end + 1;
        }
    }
    return res;
};

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

Idea:

• Treat this as an elevator
• The letter trend is from the top to the bottom, and then from the bottom to the top as the elevator, so only need to build n(numRows) level strings elevator, each string represents a layer(level)
• every time to visit a layer(level) while loop through the String s, store that letter into visiting layer(level)
• merge all the layers to get the final answer

Solution:

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if (numRows === 1) return s;
        
    let levels = [];
    for (let i = 0; i < numRows; i++) {
        levels[i] = [];
    }
    let down = true;
    const n = s.length;
    let index = 0;
    for (let i =  0; i < n; i++) {
        if (down) {
            let end = index >= numRows - 1;
            if (end) down = false;
            levels[index].push(s[i]);
            index = end ? index - 1: index + 1;
        } else {
            let top = index <= 0;
            if (top) down = true;
            levels[index].push(s[i]);
            index = top ? index + 1: index - 1;
        }
    }
    let res = "";
    for (let i = 0; i < numRows; i++) {
        res += levels[i].join('');
    }
    return res;
};