Efficient Algorithm in Java for Solving the Maximize The Number Problem

 Problem

Problem_Link

Problem Solving Method

• Goal: Swap the 1 at the end and the 0 at the front.
• Condition: The number of swaps must be less than the given k.
• Use StringBuilder: Since the string needs to be swapped, StringBuilder is the most efficient method.
• The last 1 must only be needed when the number of swaps is less than k.
• The loop ends when:
  1. The number of swaps is greater than k.
  2. The loop is performed for the given length.

So, two pointers are used. 

The first pointer (i) iterates to find 0, and the second pointer (lastOneIndex) finds the 1 at the end.

After both pointers have found their values, they swap them, and if the number of swaps exceeds K, the loop stops.

Time complexity: O(n), Space complexity: O(n)

class Solution {
    public static String maximumNumber(String S, int K) {
        // Convert string S to StringBuilder for easy modification
        StringBuilder sb = new StringBuilder(S);
        int n = S.length(); // Length of the string
        int lastOneIndex = n - 1; // Variable to store the index of the last 1
        int counter = 0; // Variable to store the number of swaps

        // Find the index of the last 1 in the back
        // This index must be greater than i and the number of swaps must be less than K.
        for (int i = 0; i < n && counter < K; i++) {
            while (lastOneIndex > i && sb.charAt(lastOneIndex) == '0') {
                lastOneIndex--;
            }

            // If the current position is 0 and the last 1 is behind the current position, swap
            if (sb.charAt(i) == '0' && lastOneIndex > i) {
                sb.setCharAt(i, '1'); // Change the current position's 0 to 1
                sb.setCharAt(lastOneIndex, '0'); // Change the last 1 position to 0
                counter++; // Increase the number of swaps
            }
        }

        // Return the modified string
        return sb.toString();
    }
}