Problem Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects. ...
Problem Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given “hello/world:here”, return “here/world:hello” Follow-up Does your solution work for the following cases: "hello/world:here/", "hello//world:here" Examples Example 1: Input: s = hello/world:here Output: here/world:hello Solution Method 1 - Using stack to store words and queue for delimiters Code Java class Solution { public String reverseWords(String s) { Stack<String> stack = new Stack<>(); Queue<String> queue = new LinkedList<>(); StringBuilder word = new StringBuilder(); int i = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isLetterOrDigit(c)) { word.append(c); i++; } else { if (word.length() > 0) { stack.push(word.toString()); } word = new StringBuilder(); // clear word for next word StringBuilder delim = new StringBuilder(); delim.append(c); i++; // tracking continuous delimiter to add to queue while (i < s.length() && !Character.isLetterOrDigit(s.charAt(i))) { delim.append(c); i++; } queue.add(delim.toString()); } } // if string ends with words if (word.length() != 0) { stack.push(word.toString()); } boolean isWordFirst = Character.isLetterOrDigit(s.charAt(0)); StringBuilder sb = new StringBuilder(); // if word is not first, add 1 entry from queue if (!isWordFirst) { if (!queue.isEmpty()) { sb.append(queue.remove()); } } // now put 1 element from either till not empty while (!stack.isEmpty() || !queue.isEmpty()) { if (!stack.isEmpty()) { sb.append(stack.pop()); } if (!queue.isEmpty()) { sb.append(queue.remove()); } } return sb.toString(); } } ...
Problem An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters: 'A': Absent. 'L': Late. 'P': Present. Any student is eligible for an attendance award if they meet both of the following criteria: The student was absent ('A') for strictly fewer than 2 days total. The student was never late ('L') for 3 or more consecutive days. Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 10^9 + 7. ...
Problem Given a list of words, list of single letters (might be repeating) and score of every character. Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times). It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', … ,'z' is given by score[0], score[1], … , score[25] respectively. ...
Problem There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker. We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules: Every worker in the paid group must be paid at least their minimum wage expectation. In the group, each worker’s pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker. Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within $10^{-5}$ of the actual answer will be accepted. ...
Problem A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. ...
Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k. OR You are given an integer array nums and two integers indexDiff and valueDiff. Find a pair of indices (i, j) such that: ...
Problem Given that integers are read from a data stream. Find median of elements read so for in efficient way. OR Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) ...
Problem Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one. The closest is defined as the absolute difference minimized between two integers. Examples Example 1: Input: n = "123" Output: "121" Example 2: Input: n = "1" Output: "0" Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0. ...
Problem Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Examples Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. ...