Algorithm - Programmers & LeetCode Problems 8

Programmers Problem lev.2 JadenCase 문자열 만들기

• JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고)
• 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
• 숫자는 단어의 첫 문자로만 나옵니다.
• 숫자로만 이루어진 단어는 없습니다.
• 공백문자가 연속해서 나올 수 있습니다.

입출력 예

s	return
"3people unFollowed me"	"3people Unfollowed Me"
"for the last week"	"For The Last Week"

Solution

function solution(s) {
    const strArr = s.split(' ');
    return strArr.map(convertToJadenCase).join(' ');
}

function convertToJadenCase(str) {
    let JadenCaseStr = '';
    
    for (let i = 0; i < str.length; i++) {
        const letter = str[i];
        if (i === 0) {
            JadenCaseStr += letter.toUpperCase();
        } else {
            JadenCaseStr += letter.toLowerCase();
        }
    }
    
    return JadenCaseStr;
}

LeetCode Problem 1249. Minimum Remove to Make Valid Parentheses

• Given a string s of '(' , ')' and lowercase English characters.

• Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

• Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or

• It can be written as AB (A concatenated with B), where A and B are valid strings, or

• It can be written as (A), where A is a valid string.

Examples

• Example 1:

  • Input: s = "lee(t(c)o)de)"
  • Output: "lee(t(c)o)de"
  • Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

• Example 2:

  • Input: s = "a)b(c)d"
  • Output: "ab(c)d"

• Example 3:

  • Input: s = "))(("
  • Output: ""
  • Explanation: An empty string is also valid.

Constraints

• 1 <= s.length <= 10^5
• s[i] is either '(' , ')', or lowercase English letter.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    const stack = [];
    const strArr = s.split('');

    for (let i = 0; i < strArr.length; i++) {
        if (strArr[i] === '(') {
            stack.push(i);
        } else if (strArr[i] === ')') {
            if (stack.length && strArr[stack[stack.length -1]] ===  '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
    }

    for (const index of stack) {
        strArr[index] = '';
    }

    return strArr.join('');
};

LeetCode Problem 1358. Number of Substrings Containing All Three Characters

• Given a string s consisting only of characters a, b and c.

• Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Examples

• Example 1:

  • Input: s = "abcabc"
  • Output: 10
  • Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

• Example 2:

  • Input: s = "aaacb"
  • Output: 3
  • Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

• Example 3:

  • Input: s = "abc"
  • Output: 1

Constraints

• 3 <= s.length <= 5 x 10^4
• s only consists of a, b or c characters.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    let aCount = 0, bCount = 0, cCount = 0, result = 0;

    for (let left = 0, right = 0; right < s.length; right++) {
        if (s[right] === 'a') {
            aCount++;
        }
        if (s[right] === 'b') {
            bCount++;
        }
        if (s[right] === 'c') {
            cCount++;
        }

        while (aCount && bCount && cCount) {
            result += s.length - right;
            if (s[left] === 'a') {
                aCount--;
            }
            if (s[left] === 'b') {
                bCount--;
            }
            if (s[left] === 'c') {
                cCount--;
            }
            left++;
        }
    }

    return result;
};

LeetCode Problem 1763. Longest Nice Substring

• A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase.
  • For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.
• Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Examples

• Example 1:

  • Input: s = "YazaAay"
  • Output: "aAa"
  • Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
    • "aAa" is the longest nice substring.

• Example 2:

  • Input: s = "Bb"
  • Output: "Bb"
  • Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

• Example 3:

  • Input: s = "c"
  • Output: ""
  • Explanation: There are no nice substrings.

Constraints

• 1 <= s.length <= 100
• s consists of uppercase and lowercase English letters.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestNiceSubstring = function(s) {
    const strSet = new Set();
    
    for (const letter of s) {
        strSet.add(letter);
    }

    for (let i = 0; i < s.length; i++) {
        const upperCaseLetter = s[i].toUpperCase();
        const lowerCaseLetter = s[i].toLowerCase();

        if (strSet.has(upperCaseLetter) && strSet.has(lowerCaseLetter)) {
        continue;
        }

        const prevStr = longestNiceSubstring(s.substring(0, i));
        const nextStr = longestNiceSubstring(s.substring(i + 1));

        return prevStr.length >= nextStr.length ? prevStr : nextStr;  
    }

    return s;
};