83. Remove Duplicates from Sorted List

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]

ex1

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

ex2

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

Solution#

Solution