Dmitrii Volyx

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

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. ...