3.

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

 0 <= s.length <= 5 * 10 4

 s consists of English letters, digits, symbols and spaces.

Solutions:

C++

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int n = s.length();

int res = 0;

for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {

 if (checkRepetition(s, i, j)) {

res = max(res, j - i + 1);

return res;

bool checkRepetition(string& s, int start, int end) {

unordered_set<char> chars;

for (int i = start; i <= end; i++) {

char c = s[i];

if(chars.count(c)){

return false;

chars.insert(c);

return true;

};

Java
public class Solution {

public int lengthOfLongestSubstring(String s) {

int n = s.length();

int res = 0;

for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {

if (checkRepetition(s, i, j)) {

res = Math.max(res, j - i + 1);

return res;

private boolean checkRepetition(String s, int start, int end) {

Set<Character> chars = new HashSet<>();

for (int i = start; i <= end; i++) {

char c = s.charAt(i);

if(chars.contains(c)){

return false;

chars.add(c);
 }

return true;

Python

public class Solution {

public int lengthOfLongestSubstring(String s) {

int n = s.length();

int res = 0;

for (int i = 0; i < n; i++) {

for (int j = i; j < n; j++) {

if (checkRepetition(s, i, j)) {

res = Math.max(res, j - i + 1);

return res;

private boolean checkRepetition(String s, int start, int end) {

Set<Character> chars = new HashSet<>();

 for (int i = start; i <= end; i++) {

char c = s.charAt(i);

if(chars.contains(c)){

return false;

chars.add(c);

return true;

}
20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Constraints:
  1 <= s.length <= 10 4

 s consists of parentheses only '()[]{}'.

Solutions:

Java

class Solution {

// Hash table that takes care of the mappings.

private HashMap<Character, Character> mappings;

// Initialize hash map with mappings. This simply makes the code easier to read.

public Solution() {

this.mappings = new HashMap<Character, Character>();

this.mappings.put(')', '(');

this.mappings.put('}', '{');

this.mappings.put(']', '[');

public boolean isValid(String s) {

// Initialize a stack to be used in the algorithm.

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {

char c = s.charAt(i);

// If the current character is a closing bracket.

 if (this.mappings.containsKey(c)) {

python:

class Solution(object):

def isValid(self, s):

"""

:type s: str

:rtype: bool

"""

# The stack to keep track of opening brackets.

stack = []

# Hash map for keeping track of mappings. This keeps the code very clean.

# Also makes adding more types of parenthesis easier

mapping = {")": "(", "}": "{", "]": "["}

# For every bracket in the expression.

for char in s:

# If the character is an closing bracket

if char in mapping:

# Pop the topmost element from the stack, if it is non empty

# Otherwise assign a dummy value of '#' to the top_element variable

top_element = stack.pop() if stack else '#'

29. Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -
2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2 , 2 − 1]. For
31 31

this problem, if the quotient is strictly greater than 2 - 1, then return 2 - 1, and if the quotient is strictly less than -2 , then return -
31 31 31

2 .
31

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

 -231
<= dividend, divisor <= 2
31
- 1
 divisor != 0

SOLUTIONS:

C++

int divide(int dividend, int divisor) {

// Special case: overflow.

if (dividend == INT_MIN && divisor == -1) {

return INT_MAX;

/* We need to convert both numbers to negatives

* for the reasons explained above.

* Also, we count the number of negatives signs. */

int negatives = 2;

if (dividend > 0) {

negatives--;

dividend = -dividend;

if (divisor > 0) {

negatives--;

divisor = -divisor;

/* Count how many times the divisor has to be added

* to get the dividend. This is the quotient. */

int quotient = 0;

while (dividend - divisor <= 0) {

dividend -= divisor;

quotient--;

/* If there was originally one negative sign, then

* the quotient remains negative. Otherwise, switch

* it to positive. */

if (negatives != 1) {

return -quotient;

}
 return quotient;

JAVA

public int divide(int dividend, int divisor) {

// Special case: overflow.

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

/* We need to convert both numbers to negatives

* for the reasons explained above.

* Also, we count the number of negatives signs. */

int negatives = 2;

if (dividend > 0) {

negatives--;

dividend = -dividend;

if (divisor > 0) {

negatives--;

divisor = -divisor;

/* Count how many times the divisor has to be added

* to get the dividend. This is the quotient. */

 int quotient = 0;

while (dividend - divisor <= 0) {

quotient--;

dividend -= divisor;

/* If there was originally one negative sign, then

* the quotient remains negative. Otherwise, switch

* it to positive. */

if (negatives != 1) {

quotient = -quotient;

return quotient;

PYTHON

def divide(self, dividend: int, divisor: int) -> int:

# Constants.

MAX_INT = 2147483647 # 2**31 - 1

MIN_INT = -2147483648 # -2**31

# Special case: overflow.

if dividend == MIN_INT and divisor == -1:

return MAX_INT
 # We need to convert both numbers to negatives

# for the reasons explained above.

# Also, we count the number of negatives signs.

negatives = 2

if dividend > 0:

negatives -= 1

dividend = -dividend

if divisor > 0:

negatives -= 1

divisor = -divisor

# Count how many times the divisor has to be

# added to get the dividend. This is the quotient.

quotient = 0

while dividend - divisor <= 0:

quotient -= 1

dividend -= divisor

# If there was originally one negative sign, then

# the quotient remains negative. Otherwise, switch

# it to positive.

return -quotient if negatives != 1 else quotient

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly
once.
Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

 1 <= strs.length <= 10 4

 0 <= strs[i].length <= 100

 strs[i] consists of lowercase English letters.

SOLUTIONS:

JAVA

class Solution {

public List<List<String>> groupAnagrams(String[] strs) {

if (strs.length == 0) return new ArrayList();

Map<String, List> ans = new HashMap<String, List>();

for (String s : strs) {

char[] ca = s.toCharArray();

Arrays.sort(ca);

String key = String.valueOf(ca);

if (!ans.containsKey(key)) ans.put(key, new ArrayList());

ans.get(key).add(s);

return new ArrayList(ans.values());

}
}

PYTHON

class Solution(object):

def groupAnagrams(self, strs):

ans = collections.defaultdict(list)

for s in strs:

ans[tuple(sorted(s))].append(s)

return ans.values()
55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your
maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]

Output: false

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible
to reach the last index.

Constraints:

 1 <= nums.length <= 10 4

 0 <= nums[i] <= 10 5

SOLUTIONS:

JAVA

enum Index {

GOOD, BAD, UNKNOWN

}
public class Solution {

Index[] memo;

public boolean canJumpFromPosition(int position, int[] nums) {

if (memo[position] != Index.UNKNOWN) {

return memo[position] == Index.GOOD ? true : false;

int furthestJump = Math.min(position + nums[position], nums.length - 1);

for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {

if (canJumpFromPosition(nextPosition, nums)) {

memo[position] = Index.GOOD;

return true;

memo[position] = Index.BAD;

return false;

public boolean canJump(int[] nums) {

memo = new Index[nums.length];

for (int i = 0; i < memo.length; i++) {

memo[i] = Index.UNKNOWN;
 }

memo[memo.length - 1] = Index.GOOD;

return canJumpFromPosition(0, nums);

}
134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the i station is gas[i].
th

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i station to its next (i + 1) station. You begin the
th th

journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise
direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output: 3

Explanation:

Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 4. Your tank = 4 - 1 + 5 = 8

Travel to station 0. Your tank = 8 - 2 + 1 = 7

Travel to station 1. Your tank = 7 - 3 + 2 = 6

Travel to station 2. Your tank = 6 - 4 + 3 = 5

Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.

Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation:

You can't start at station 0 or 1, as there is not enough gas to travel to the next station.

Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Travel to station 0. Your tank = 4 - 3 + 2 = 3

Travel to station 1. Your tank = 3 - 3 + 3 = 3

You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.

Therefore, you can't travel around the circuit once no matter where you start.
Constraints:

 n == gas.length == cost.length
 1 <= n <= 10
5

 0 <= gas[i], cost[i] <= 10

4

SOLUTIONS:

C++

class Solution {

public:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

int currGain = 0, totalGain = 0, answer = 0;

for (int i = 0; i < gas.size(); ++i) {

// gain[i] = gas[i] - cost[i]

totalGain += gas[i] - cost[i];

currGain += gas[i] - cost[i];

// If we meet a "valley", start over from the next station

// with 0 initial gas.

if (currGain < 0) {

answer = i + 1;

currGain = 0;

return totalGain >= 0 ? answer : -1;

}
};

JAVA

class Solution {

public int canCompleteCircuit(int[] gas, int[] cost) {

int currGain = 0, totalGain = 0, answer = 0;

for (int i = 0; i < gas.length; ++i) {

// gain[i] = gas[i] - cost[i]

totalGain += gas[i] - cost[i];

currGain += gas[i] - cost[i];

// If we meet a "valley", start over from the next station

// with 0 initial gas.

if (currGain < 0) {

answer = i + 1;

currGain = 0;

return totalGain >= 0 ? answer : -1;

PYTHON3

class Solution:

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

 total_gain = 0

curr_gain = 0

answer = 0

for i in range(len(gas)):

# gain[i] = gas[i] - cost[i]

total_gain += gas[i] - cost[i]

curr_gain += gas[i] - cost[i]

# If we meet a "valley", start over from the next station

# with 0 initial gas.

if curr_gain < 0:

curr_gain = 0

answer = i + 1

return answer if total_gain >= 0 else -1

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

 LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
 int get(int key) Return the value of the key if the key exists, otherwise return -1.
 void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If
the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // cache is {1=1}

lRUCache.put(2, 2); // cache is {1=1, 2=2}

lRUCache.get(1); // return 1

lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}

lRUCache.get(2); // returns -1 (not found)

lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}

lRUCache.get(1); // return -1 (not found)

lRUCache.get(3); // return 3

lRUCache.get(4); // return 4

Constraints:

 1 <= capacity <= 3000

 0 <= key <= 10 4

 0 <= value <= 10 5

 At most 2 * 10 calls will be made to get and put.

5

Solutions:

C++

void add(Node *node) {

Node *previousEnd = tail->prev;

previousEnd->next = node;

node->prev = previousEnd;

node->next = tail;

tail->prev = node;

Java

public void add(ListNode node) {

ListNode previousEnd = tail.prev;

 previousEnd.next = node;

node.prev = previousEnd;

node.next = tail;

tail.prev = node;

Python3

def add(self, node):

previous_end = self.tail.prev

previous_end.next = node

node.prev = previous_end

node.next = self.tail

self.tail.prev = node
273. Integer to English Words

Convert a non-negative integer num to its English words representation.

Example 1:

Input: num = 123

Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345

Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567

Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Constraints:

 0 <= num <= 2 31

- 1

Solutions:

java
class Solution {

public String one(int num) {

switch(num) {

case 1: return "One";

case 2: return "Two";

case 3: return "Three";

case 4: return "Four";

case 5: return "Five";

case 6: return "Six";

case 7: return "Seven";

case 8: return "Eight";

case 9: return "Nine";

return "";

public String twoLessThan20(int num) {

switch(num) {

case 10: return "Ten";

case 11: return "Eleven";

case 12: return "Twelve";

case 13: return "Thirteen";

case 14: return "Fourteen";

case 15: return "Fifteen";

case 16: return "Sixteen";

 case 17: return "Seventeen";

case 18: return "Eighteen";

case 19: return "Nineteen";

return "";

public String ten(int num) {

switch(num) {

case 2: return "Twenty";

case 3: return "Thirty";

case 4: return "Forty";

case 5: return "Fifty";

case 6: return "Sixty";

case 7: return "Seventy";

case 8: return "Eighty";

case 9: return "Ninety";

return "";

public String two(int num) {

if (num == 0)

return "";

else if (num < 10)

 return one(num);

else if (num < 20)

return twoLessThan20(num);

else {

int tenner = num / 10;

int rest = num - tenner * 10;

if (rest != 0)

return ten(tenner) + " " + one(rest);

else

return ten(tenner);

public String three(int num) {

int hundred = num / 100;

int rest = num - hundred * 100;

String res = "";

if (hundred*rest != 0)

res = one(hundred) + " Hundred " + two(rest);

else if ((hundred == 0) && (rest != 0))

res = two(rest);

else if ((hundred != 0) && (rest == 0))

res = one(hundred) + " Hundred";

return res;

}
public String numberToWords(int num) {

if (num == 0)

return "Zero";

int billion = num / 1000000000;

int million = (num - billion * 1000000000) / 1000000;

int thousand = (num - billion * 1000000000 - million * 1000000) / 1000;

int rest = num - billion * 1000000000 - million * 1000000 - thousand * 1000;

String result = "";

if (billion != 0)

result = three(billion) + " Billion";

if (million != 0) {

if (! result.isEmpty())

result += " ";

result += three(million) + " Million";

if (thousand != 0) {

if (! result.isEmpty())

result += " ";

result += three(thousand) + " Thousand";

if (rest != 0) {

if (! result.isEmpty())
 result += " ";

result += three(rest);

return result;

Python:

class Solution:

def numberToWords(self, num):

"""

:type num: int

:rtype: str

"""

def one(num):

switcher = {

1: 'One',

2: 'Two',

3: 'Three',

4: 'Four',

5: 'Five',

6: 'Six',

7: 'Seven',

8: 'Eight',

9: 'Nine'

}
 return switcher.get(num)

def two_less_20(num):

switcher = {

10: 'Ten',

11: 'Eleven',

12: 'Twelve',

13: 'Thirteen',

14: 'Fourteen',

15: 'Fifteen',

16: 'Sixteen',

17: 'Seventeen',

18: 'Eighteen',

19: 'Nineteen'

return switcher.get(num)

def ten(num):

switcher = {

2: 'Twenty',

3: 'Thirty',

4: 'Forty',

5: 'Fifty',

6: 'Sixty',

7: 'Seventy',
 8: 'Eighty',

9: 'Ninety'

return switcher.get(num)

def two(num):

if not num:

return ''

elif num < 10:

return one(num)

elif num < 20:

return two_less_20(num)

else:

tenner = num // 10

rest = num - tenner * 10

return ten(tenner) + ' ' + one(rest) if rest else ten(tenner)

def three(num):

hundred = num // 100

rest = num - hundred * 100

if hundred and rest:

return one(hundred) + ' Hundred ' + two(rest)

elif not hundred and rest:

return two(rest)
 elif hundred and not rest:

return one(hundred) + ' Hundred'

billion = num // 1000000000

million = (num - billion * 1000000000) // 1000000

thousand = (num - billion * 1000000000 - million * 1000000) // 1000

rest = num - billion * 1000000000 - million * 1000000 - thousand * 1000

if not num:

return 'Zero'

result = ''

if billion:

result = three(billion) + ' Billion'

if million:

result += ' ' if result else ''

result += three(million) + ' Million'

if thousand:

result += ' ' if result else ''

result += three(thousand) + ' Thousand'

if rest:

result += ' ' if result else ''

result += three(rest)

return result
300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

Constraints:

 1 <= nums.length <= 2500

 -10 <= nums[i] <= 10
4 4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solutions:

Java

class Solution {

public int lengthOfLIS(int[] nums) {

int[] dp = new int[nums.length];

Arrays.fill(dp, 1);

for (int i = 1; i < nums.length; i++) {

for (int j = 0; j < i; j++) {

if (nums[i] > nums[j]) {

dp[i] = Math.max(dp[i], dp[j] + 1);

}
 }

int longest = 0;

for (int c: dp) {

longest = Math.max(longest, c);

return longest;

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

dp = [1] * len(nums)

for i in range(1, len(nums)):

for j in range(i):

if nums[i] > nums[j]:

dp[i] = max(dp[i], dp[j] + 1)

return max(dp)
316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in
lexicographical order among all possible results.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"

Output: "acdb"

Constraints:

 1 <= s.length <= 10 4

 s consists of lowercase English letters.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Solutions:

Java

public class Solution {

public String removeDuplicateLetters(String s) {

// find pos - the index of the leftmost letter in our solution

// we create a counter and end the iteration once the suffix doesn't have each unique character

// pos will be the index of the smallest character we encounter before the iteration ends

int[] cnt = new int[26];

int pos = 0;

for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) < s.charAt(pos)) pos = i;

if (--cnt[s.charAt(i) - 'a'] == 0) break;

// our answer is the leftmost letter plus the recursive call on the remainder of the string

// note that we have to get rid of further occurrences of s[pos] to ensure that there are no
duplicates

return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll(""

+ s.charAt(pos), ""));
 }

Python:

from collections import Counter

class Solution:

def removeDuplicateLetters(self, s: str) -> str:

# find pos - the index of the leftmost letter in our solution

# we create a counter and end the iteration once the suffix doesn't have each unique character

# pos will be the index of the smallest character we encounter before the iteration ends

c = Counter(s)

pos = 0

for i in range(len(s)):

if s[i] < s[pos]: pos = i

c[s[i]] -=1

if c[s[i]] == 0: break

# our answer is the leftmost letter plus the recursive call on the remainder of the string

# note we have to get rid of further occurrences of s[pos] to ensure that there are no duplicates

return s[pos] + self.removeDuplicateLetters(s[pos:].replace(s[pos], "")) if s else ''

394. Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square
brackets is being repeated exactly k times. Note that k is guaranteed to be a positive
integer.

You may assume that the input string is always valid; there are no extra white spaces,
square brackets are well-formed, etc. Furthermore, you may assume that the original
data does not contain any digits and that digits are only for those repeat numbers, k.
For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

Example 1:

Input: s = "3[a]2[bc]"

Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"

Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"

Output: "abcabccdcdcdef"

Constraints:

 1 <= s.length <= 30

 s consists of lowercase English letters, digits, and square brackets '[]'.
 s is guaranteed to be a valid input.
 All the integers in s are in the range [1, 300].

Solutions:

C++

class Solution {

public:

string decodeString(string s) {

stack<char> stack;

for (int i = 0; i < s.length(); i++) {

if (s[i] == ']') {
 string decodedString = "";

// get the encoded string

while (stack.top() != '[') {

decodedString += stack.top();

stack.pop();

// pop [ from stack

stack.pop();

int base = 1;

int k = 0;

// get the number k

while (!stack.empty() && isdigit(stack.top())) {

k = k + (stack.top() - '0') * base;

stack.pop();

base *= 10;

int currentLen = decodedString.size();

// decode k[decodedString], by pushing decodedString k times into stack

while (k != 0) {

for (int j = decodedString.size() - 1; j >= 0; j--) {

stack.push(decodedString[j]);

k--;

}
 // push the current character to stack

else {

stack.push(s[i]);

// get the result from stack

string result;

for (int i = stack.size() - 1; i >= 0; i--) {

result = stack.top() + result;

stack.pop();

return result;

};

Java

class Solution {

public String decodeString(String s) {

Stack<Character> stack = new Stack<>();

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == ']') {

List<Character> decodedString = new ArrayList<>();

// get the encoded string

while (stack.peek() != '[') {

decodedString.add(stack.pop());

}
 // pop [ from the stack

stack.pop();

int base = 1;

int k = 0;

// get the number k

while (!stack.isEmpty() && Character.isDigit(stack.peek())) {

k = k + (stack.pop() - '0') * base;

base *= 10;

// decode k[decodedString], by pushing decodedString k times into stack

while (k != 0) {

for (int j = decodedString.size() - 1; j >= 0; j--) {

stack.push(decodedString.get(j));

k--;

// push the current character to stack

else {

stack.push(s.charAt(i));

// get the result from stack

char[] result = new char[stack.size()];

for (int i = result.length - 1; i >= 0; i--) {

 result[i] = stack.pop();

return new String(result);

}
697. Degree of an Array

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its
elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: nums = [1,2,2,3,1]

Output: 2

Explanation:

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

Input: nums = [1,2,2,3,1,4,2]

Output: 6

Explanation:

The degree is 3 because the element 2 is repeated 3 times.

So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Constraints:

 nums.length will be between 1 and 50,000.

 nums[i] will be an integer between 0 and 49,999.

Solutions:

Python

class Solution(object):

def findShortestSubArray(self, nums):

 left, right, count = {}, {}, {}

for i, x in enumerate(nums):

if x not in left: left[x] = i

right[x] = i

count[x] = count.get(x, 0) + 1

ans = len(nums)

degree = max(count.values())

for x in count:

if count[x] == degree:

ans = min(ans, right[x] - left[x] + 1)

return ans

Java

class Solution {

public int findShortestSubArray(int[] nums) {

Map<Integer, Integer> left = new HashMap(),

right = new HashMap(), count = new HashMap();

for (int i = 0; i < nums.length; i++) {

int x = nums[i];

if (left.get(x) == null) left.put(x, i);

right.put(x, i);

count.put(x, count.getOrDefault(x, 0) + 1);

int ans = nums.length;

int degree = Collections.max(count.values());

for (int x: count.keySet()) {

if (count.get(x) == degree) {

ans = Math.min(ans, right.get(x) - left.get(x) + 1);

}
 return ans;

735. Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left).
Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will
explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]

Output: [5,10]

Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]

Output: []

Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]

Output: [10]

Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

 2 <= asteroids.length <= 10 4

 -1000 <= asteroids[i] <= 1000

 asteroids[i] != 0

Solutions:

C++

class Solution {

public:

vector<int> asteroidCollision(vector<int>& asteroids) {

stack<int> st;
 for (int asteroid : asteroids) {

int flag = 1;

while (!st.empty() && (st.top() > 0 && asteroid < 0)) {

// If the top asteroid in the stack is smaller, then it will explode.

// Hence pop it from the stack, also continue with the next asteroid in the
stack.

if (abs(st.top()) < abs(asteroid)) {

st.pop();

continue;

// If both asteroids are the same size, then both asteroids will explode.

// Pop the asteroid from the stack; also, we won't push the current asteroid to
the stack.

else if (abs(st.top()) == abs(asteroid)) {

st.pop();

// If we reach here, the current asteroid will be destroyed

// Hence, we should not add it to the stack

flag = 0;

break;

if (flag) {

st.push(asteroid);

// Add the asteroids from the stack to the vector in the reverse order.

vector<int> remainingAsteroids (st.size());

for (int i = remainingAsteroids.size() - 1; i >= 0; i--){

remainingAsteroids[i] = st.top();
 st.pop();

return remainingAsteroids;

};

Java

class Solution {

public int[] asteroidCollision(int[] asteroids) {

Stack<Integer> st = new Stack<Integer>();

for (int asteroid : asteroids) {

boolean flag = true;

while (!st.isEmpty() && (st.peek() > 0 && asteroid < 0)) {

// If the top asteroid in the stack is smaller, then it will explode.

// Hence pop it from the stack, also continue with the next asteroid in the
stack.

if (Math.abs(st.peek()) < Math.abs(asteroid)) {

st.pop();

continue;

// If both asteroids have the same size, then both asteroids will explode.

// Pop the asteroid from the stack; also, we won't push the current asteroid to
the stack.

else if (Math.abs(st.peek()) == Math.abs(asteroid)) {

st.pop();

// If we reach here, the current asteroid will be destroyed

// Hence, we should not add it to the stack

flag = false;

break;
 }

if (flag) {

st.push(asteroid);

// Add the asteroids from the stack to the vector in the reverse order.

int[] remainingAsteroids = new int[st.size()];

for (int i = remainingAsteroids.length - 1; i >= 0; i--) {

remainingAsteroids[i] = st.peek();

st.pop();

return remainingAsteroids;

1751. Maximum Number of Events That Can Be Attended II

You are given an array of events where events[i] = [startDay , endDay , value ]. The i event starts at startDay and ends at endDay ,
i i i
th
i i

and if you attend this event, you will receive a value of value . You are also given an integer k which represents the maximum number of
i

events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day
is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Example 1:
Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2

Output: 7

Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2

Output: 10

Explanation: Choose event 2 for a total value of 10.

Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:
Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3

Output: 9

Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints:

 1 <= k <= events.length

 1 <= k * events.length <= 10 6

 1 <= startDay <= endDay <= 10

i i
9

 1 <= value <= 10

i
6

Solutions:

Java

class Solution {

public int maxValue(int[][] events, int k) {

Arrays.sort(events, (a, b) -> a[0] - b[0]);

int n = events.length;

dp = new int[k + 1][n];

for (int[] row : dp) {

Arrays.fill(row, -1);
 }

return dfs(0, k, events);

private int[][] dp;

private int dfs(int curIndex, int count, int[][] events) {

if (count == 0 || curIndex == events.length) {

return 0;

if (dp[count][curIndex] != -1) {

return dp[count][curIndex];

int nextIndex = bisectRight(events, events[curIndex][1]);

dp[count][curIndex] = Math.max(dfs(curIndex + 1, count, events), events[curIndex][2] +

dfs(nextIndex, count - 1, events));

return dp[count][curIndex];

public static int bisectRight(int[][] events, int target) {

int left = 0, right = events.length;

while (left < right) {

int mid = (left + right) / 2;

if (events[mid][0] <= target) {

left = mid + 1;

} else {

right = mid;

return left;

}
}

Python

class Solution:

def maxValue(self, events: List[List[int]], k: int) -> int:

events.sort()

n = len(events)

starts = [start for start, end, value in events]

dp = [[-1] * n for _ in range(k + 1)]

def dfs(cur_index, count):

if count == 0 or cur_index == n:

return 0

if dp[count][cur_index] != -1:

return dp[count][cur_index]

# Find the nearest available event after attending event 0.

next_index = bisect_right(starts, events[cur_index][1])

dp[count][cur_index] = max(dfs(cur_index + 1, count), events[cur_index][2] +

dfs(next_index, count - 1))

return dp[count][cur_index]

return dfs(0, k)

2439. Minimize Maximum of Array

You are given a 0-indexed array nums comprising of n non-negative integers.

In one operation, you must:

 Choose an integer i such that 1 <= i < n and nums[i] > 0.

 Decrease nums[i] by 1.
 Increase nums[i - 1] by 1.

Return the minimum possible value of the maximum integer of nums after performing any number of operations.

Example 1:
Input: nums = [3,7,1,6]

Output: 5

Explanation:

One set of optimal operations is as follows:

1. Choose i = 1, and nums becomes [4,6,1,6].

2. Choose i = 3, and nums becomes [4,6,2,5].

3. Choose i = 1, and nums becomes [5,5,2,5].

The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.

Therefore, we return 5.

Example 2:

Input: nums = [10,1]

Output: 10

Explanation:

It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.

Constraints:

 n == nums.length
 2 <= n <= 10
5

 0 <= nums[i] <= 10 9

Solutions:
C++
class Solution {
public:
int minimizeArrayValue(vector<int>& nums) {
// Initialize answer and the prefix sum.
long long answer = 0, prefixSum = 0;

// Iterate over nums, update prefix sum and answer.

for (int i = 0; i < nums.size(); ++i) {
prefixSum += nums[i];
 answer = max(answer, (prefixSum + i) / (i + 1));
}

return answer;
}
};
Java
class Solution {
public int minimizeArrayValue(int[] nums) {
// Initialize answer and the prefix sum.
long answer = 0, prefixSum = 0;

// Iterate over nums, update prefix sum and answer.

for (int i = 0; i < nums.length; ++i) {
prefixSum += nums[i];
answer = Math.max(answer, (prefixSum + i) / (i + 1));
}

return (int)answer;
}
}
Python3
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
# Initialize answer and the prefix sum.
answer = 0
 prefix_sum = 0

# Iterate over nums, update prefix sum and answer.

for i in range(len(nums)):
prefix_sum += nums[i]
answer = max(answer, math.ceil(prefix_sum / (i + 1)))

return answer
2472. Maximum Number of Non-overlapping Palindrome Substrings

You are given a string s and a positive integer k.

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

 The length of each substring is at least k.

 Each substring is a palindrome.

Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abaccdbbd", k = 3

Output: 2

Explanation: We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have
a length of at least k = 3.

It can be shown that we cannot find a selection with more than two valid substrings.

Example 2:

Input: s = "adbcda", k = 2

Output: 0

Explanation: There is no palindrome substring of length at least 2 in the string.

Constraints:

 1 <= k <= s.length <= 2000

 s consists of lowercase English letters.

Solutions:
2539. Count the Number of Good Subsequences

A subsequence of a string is good if it is not empty and the frequency of each one of its characters is the same.

Given a string s, return the number of good subsequences of s. Since the answer may be too large, return it modulo 10 + 7.
9

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the
remaining characters.

Example 1:

Input: s = "aabb"

Output: 11

Explanation: The total number of subsequences is 2 . There are five subsequences which are not good: "aabb", "aabb",
4

"aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is 2 -5 = 11. 4

Example 2:

Input: s = "leet"

Output: 12

Explanation: There are four subsequences which are not good: "leet", "leet", "leet", and the empty subsequence. Hence,
the number of good subsequences is 2 -4 = 12.
4

Example 3:

Input: s = "abcd"

Output: 15

Explanation: All of the non-empty subsequences are good subsequences. Hence, the number of good subsequences is 2 -1 = 4

15.

Constraints:

 1 <= s.length <= 10 4

 s consists of only lowercase English letters.

Solutions: