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