Leetcode

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; } }

1099. Two Sum Less Than K Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1. Example 1: Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60. Example 2: Input: nums = [10,20,30], k = 15 Output: -1 Explanation: In this case it is not possible to get a pair sum less that 15. Constraints: ...

19. Remove Nth Node From End of List Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] Constraints: The number of nodes in the list is sz. 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 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 removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next= head; ListNode walker = dummy; ListNode runner = dummy; for (int i = 0; i < n + 1; i++) { runner = runner.next; } while (runner != null) { walker = walker.next; runner = runner.next; } walker.next = walker.next.next; return dummy.next; } }

2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1: Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807. ...

523. Continuous Subarray Sum Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k. Example 1: Input: nums = [23,2,4,6,7], k = 6 Output: true Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6. Example 2: Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer. Example 3: Input: nums = [23,2,6,4,7], k = 13 Output: false Constraints: ...

67. Add Binary Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101" Constraints: 1 <= a.length, b.length <= 104 a and b consist only of ‘0’ or ‘1’ characters. Each string does not contain leading zeros except for the zero itself. Solution class Solution { public String addBinary(String a, String b) { int i = a.length() - 1; int j = b.length() - 1; int carry = 0; StringBuilder sb = new StringBuilder(); while (i >= 0 || j >= 0) { int c1 = (i >= 0) ? a.charAt(i) - '0': 0; int c2 = (j >= 0) ? b.charAt(j) - '0': 0; int c3 = c1 + c2 + carry; if (carry > 0) { carry = 0; } if (c3 == 3) { carry = 1; sb.insert(0, '1'); } else if (c3 == 2) { carry = 1; sb.insert(0, '0'); } else if (c3 == 1) { sb.insert(0, '1'); } else { sb.insert(0, '0'); } i--; j--; } if (carry > 0) { sb.insert(0, '1'); } return sb.toString(); } public String addBinary2(String a, String b) { Integer i1 = Integer.parseInt(a, 2); Integer i2 = Integer.parseInt(b, 2); return Integer.toBinaryString(i1 + i2); } }

974. Subarray Sums Divisible by K Given an array nums of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by k. Example 1: Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] Note: ...

1897. Redistribute Characters to Make All Strings Equal You are given an array of strings words (0-indexed). In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j]. Return true if you can make every string in words equal using any number of operations, and false otherwise. Example 1: Input: words = ["abc","aabc","bc"] Output: true Explanation: Move the first 'a' in words[1] to the front of words[2], to make words[1] = "abc" and words[2] = "abc". All the strings are now equal to "abc", so return true. Example 2: Input: words = ["ab","a"] Output: false Explanation: It is impossible to make all the strings equal using the operation. Constraints: ...

1898. Maximum Number of Removable Characters You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed). You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence. ...

1899. Merge Triplets to Form Target Triplet A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain. To obtain target, you may apply the following operation on triplets any number of times (possibly zero): ...