# Day 4 of LeetCode Challenge

# Problem 1: Minimum Number of Operations to Make Word K-Periodic

[link to the problem](https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741287576325/27171b50-63f6-4612-a547-2f0df9095bf9.png align="center")

```python
class Solution {
    public int minimumOperationsToMakeKPeriodic(String word, int k) {
        int maxOfAllFrequencies = 0;
        Map<String, Integer> m = new HashMap<>();

        for (int i = 0; i < word.length(); i += k) {
            String sub = word.substring(i, Math.min(i + k, word.length()));
            m.put(sub, m.getOrDefault(sub, 0) + 1);
        }
        for (int freq : m.values()) 
            maxOfAllFrequencies = Math.max(maxOfAllFrequencies, freq);
        
        return word.length() / k - maxOfAllFrequencies;
    }
}
```

---

# Problem 2: Total Distance Traveled

[link to the problem](https://leetcode.com/problems/total-distance-traveled/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741446144421/48de5515-c252-4fef-ba06-32f534d1076f.png align="center")

```python
class Solution {
    public int distanceTraveled(int mainTank, int additionalTank) {
        int num = (mainTank-1)/4>additionalTank?additionalTank:(mainTank-1)/4;
        return (mainTank + num) * 10;
    }
}
```

---

# Problem 3: Longest Common Prefix

[link to the problem](https://leetcode.com/problems/longest-common-prefix)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741456781409/7dce91bf-b45a-430f-a8a6-fe850709b8dd.png align="center")

```python
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        String pref = strs[0];
        int prefLen = pref.length();

        for (int i = 1; i < strs.length; i++) {
            String s = strs[i];
            while (prefLen > s.length() || !pref.equals(s.substring(0, prefLen))) {
                prefLen--;
                if (prefLen == 0) {
                    return "";
                }
                pref = pref.substring(0, prefLen);
            }
        }

        return pref;        
    }
}
```

---

# Problem 4: Find Subtree Sizes After Changes

[link to the problem](https://leetcode.com/problems/find-subtree-sizes-after-changes/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741457021837/c5b598ec-bac5-47e9-92e0-576f2c8bfe4b.png align="center")

```python
class Solution {
    public int[] findSubtreeSizes(int[] parent, String s) {
        int n = parent.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 1; i < n; i++) {
            adj.get(parent[i]).add(i);
        }

        int[] newParent = Arrays.copyOf(parent, n);
        Map<Character, Integer> lastSeen = new HashMap<>();
        dfsAdjustParent(0, s, adj, lastSeen, newParent);

        List<List<Integer>> finalAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            finalAdj.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            finalAdj.get(newParent[i]).add(i);
        }

        int[] answer = new int[n];
        dfsCountSubtreeSizes(0, finalAdj, answer);
        
        return answer;
    }

    public void dfsAdjustParent(int node, String s, List<List<Integer>> adj, Map<Character, Integer> lastSeen, int[] newParent) {
        char c = s.charAt(node);
        Integer prev = lastSeen.get(c);
        if (prev != null && prev != newParent[node]) {
            newParent[node] = prev;
        }

        Integer originalParent = lastSeen.put(c, node);
        for (int child : adj.get(node)) {
            dfsAdjustParent(child, s, adj, lastSeen, newParent);
        }
        if (originalParent == null) {
            lastSeen.remove(c);
        } else {
            lastSeen.put(c, originalParent);
        }
    }

    public int dfsCountSubtreeSizes(int node, List<List<Integer>> adj, int[] answer) {
        int size = 1;
        for (int child : adj.get(node)) {
            size += dfsCountSubtreeSizes(child, adj, answer);
        }
        answer[node] = size;
        return size;
    }
}
```

---

# Problem 5: Middle of the Linked List

[link to the problem](https://leetcode.com/problems/middle-of-the-linked-list/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741457513606/4d436f40-283f-4d77-a15c-d8787dce7864.png align="center")

```python
/**
 * 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 middleNode(ListNode head) {
        int len=1;
        ListNode temp = new ListNode(head.val, head.next);
        while(temp.next!=null){
            temp = temp.next; 
            len++;
        }
        len=(len/2)+1;
        System.out.println(len);
        while(len>1){
            head = head.next;
            len--;
        }
        return head;
    }
}
```