Leetcode

424. Longest Repeating Character Replacement You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations. Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. Constraints: ...

340. Longest Substring with At Most K Distinct Characters Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters. Example 1: Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3. Example 2: Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2. Constraints: ...

76. Minimum Window Substring Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”. The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string. Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Example 2: Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. Example 3: Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string. Constraints: ...

1625. Lexicographically Smallest String After Applying Operations Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Constraints: The number of nodes in the list is in the range [0, 300]. -100 <= Node.val <= 100 The list is guaranteed to be sorted in ascending order. Solution class Solution { String smallest = null; public String findLexSmallestString(String s, int a, int b) { smallest = s; Set<String> set = new HashSet<>(); dfs(s, set, a, b); return smallest; } void dfs(String current, Set<String> set, int a, int b) { if (set.contains(current)) { return; } set.add(current); if (current.compareTo(smallest) < 0) { smallest = current; } dfs(add(current, a), set, a, b); dfs(rotate(current, b), set, a, b); } String add(String s, int a) { StringBuilder sb = new StringBuilder(s); for (int i = 1; i < s.length(); i += 2) { char c = sb.charAt(i); int value = c - '0'; value += a; value = value % 10; sb.deleteCharAt(i); sb.insert(i, value); } return sb.toString(); } String rotate(String s, int b) { int len = s.length(); return s.substring(len - b, len) + s.substring(0, len - b); } }

1624. Largest Substring Between Two Equal Characters Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1. A substring is a contiguous sequence of characters within a string. Example 1: Input: s = "aa" Output: 0 Explanation: The optimal substring here is an empty substring between the two 'a's. Example 2: Input: s = "abca" Output: 2 Explanation: The optimal substring here is "bc". Example 3: Input: s = "cbzxy" Output: -1 Explanation: There are no characters that appear twice in s. Example 4: Input: s = "cabbac" Output: 4 Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "". Constraints: ...

1625. Lexicographically Smallest String After Applying Operations You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b. You can apply either of the following two operations any number of times and in any order on s: Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = “3456” and a = 5, s becomes “3951”. Rotate s to the right by b positions. For example, if s = “3456” and b = 1, s becomes “6345”. Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s. ...

206. Reverse Linked List Given the head of a singly linked list, reverse the list, and return the reversed list. Example 1: Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2: Input: head = [1,2] Output: [2,1] Example 3: Input: head = [] Output: [] Constraints: The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000 Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? ...

24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.) Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Example 2: Input: head = [] Output: [] Example 3: Input: head = [1] Output: [1] Constraints: The number of nodes in the list is in the range [0, 100]. 0 <= Node.val <= 100 Solution /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode runner = dummy; while (runner.next != null && runner.next.next != null) { ListNode r1 = runner.next; ListNode r2 = runner.next.next; runner.next = r2; r1.next = r2.next; r2.next = r1; runner = runner.next.next; } return dummy.next; } }

237. Delete Node in a Linked List Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list. Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function. ...

680. Valid Palindrome II Given a string s, return true if the s can be palindrome after deleting at most one character from it. Example 1: Input: s = "aba" Output: true Example 2: Input: s = "abca" Output: true Explanation: You could delete the character 'c'. Example 3: Input: s = "abc" Output: false Constraints: 1 <= s.length <= 105 s consists of lowercase English letters. Solution class Solution { public boolean validPalindrome(String s) { return palindrom(s, 0); } boolean palindrom(String s, int count) { int i = 0; int n = s.length(); while (i < n / 2) { char c1 = s.charAt(i); char c2 = s.charAt(n - i - 1); if (c1 == c2) { i++; continue; } else { if (count == 0) { StringBuilder sb1 = new StringBuilder(s); sb1.deleteCharAt(i); boolean res1 = palindrom(sb1.toString(), 1); if (res1) return true; StringBuilder sb2 = new StringBuilder(s); sb2.deleteCharAt(n - i - 1); return palindrom(sb2.toString(), 1); } return false; } } return true; } } Solution 2021-11-21 class Solution { public boolean validPalindrome(String s) { return validatePalindrom(s, 1, 0, s.length() - 1); } boolean validatePalindrom(String s, int deleted, int lo, int hi) { while (lo < hi) { if (s.charAt(lo) == s.charAt(hi)) { lo++; hi--; } else { if (deleted == 0) { return false; } return validatePalindrom(s, 0, lo + 1, hi) || validatePalindrom(s, 0, lo, hi - 1); } } return true; } } Solution 2022-01-22 class Solution { public boolean validPalindrome(String s) { char[] symbols = s.toCharArray(); return validPalindrome(symbols, 0, s.length() - 1, 1); } boolean validPalindrome(char[] symbols, int i, int j, int count) { while (i < j) { if (symbols[i] == symbols[j]) { i++; j--; continue; } else { if (count > 0) { return validPalindrome(symbols, i, j - 1, 0) || validPalindrome(symbols, i + 1, j, 0); } else { return false; } } } return true; } }