ZigZag Conversion

Transforming a string into a zigzag layout across a specified number of rows can be efficiently simulated. By iteraitng through each character and distributing it across a collection of buffers, we track the current row index. The traversal direction reverses automatically whenever the boundary rows are reached.

public class ZigzagTransformer {
    public String formatZigzag(String inputText, int lineCount) {
        if (lineCount < 2 || inputText == null) return inputText;

        StringBuilder[] rowBuilders = new StringBuilder[lineCount];
        for (int idx = 0; idx < lineCount; idx++) {
            rowBuilders[idx] = new StringBuilder();
        }

        int currentRow = 0;
        int stepDirection = 1;

        for (char character : inputText.toCharArray()) {
            rowBuilders[currentRow].append(character);
            
            if (currentRow == 0) {
                stepDirection = 1;
            } else if (currentRow == lineCount - 1) {
                stepDirection = -1;
            }
            currentRow += stepDirection;
        }

        StringBuilder finalResult = new StringBuilder();
        for (StringBuilder row : rowBuilders) {
            finalResult.append(row);
        }
        return finalResult.toString();
    }
}

Find the Index of the First Occurrence (Sunday Algorithm)

The Sunday algorithm optimizes substring search by precomputing a shift map. This map stores the distance from the rightmost occurrence of each character within the target pattern to the end of that pattern, plus one.

When a mismatch occurs during comparison, the algorithm inspects the character immediately following the current search window. If this character exists in the precomputed map, the window shifts accordingly; otherwise, it advances completely past the window length.

public class TextSearcher {
    public static int locateFirstMatch(String corpus, String query) {
        int corpusLength = corpus.length();
        int queryLength = query.length();

        Map<Character, Integer> skipMap = new HashMap<>();
        for (int pos = 0; pos < queryLength; pos++) {
            skipMap.put(query.charAt(pos), queryLength - pos);
        }

        int windowStart = 0;
        while (windowStart <= corpusLength - queryLength) {
            if (corpus.regionMatches(windowStart, query, 0, queryLength)) {
                return windowStart;
            }
            
            if (windowStart + queryLength >= corpusLength) return -1;
            
            char upcomingChar = corpus.charAt(windowStart + queryLength);
            windowStart += skipMap.getOrDefault(upcomingChar, queryLength + 1);
        }
        return -1;
    }
}

Text Justification

This simulation problem requires formatting text into lines of fixed width, adhering to three specific rules:

1. Last Line: Left-aligned with single spaces between words, padded with trailing spaces.
2. Single-Word Lines: Left-aligned with trailing spaces.
3. Multi-Word Lines (Non-last): Fully justified by evenly distributing spaces, with extra spaces allocated to the leftmost gaps first.

public class LineFormatter {
    public List<String> justifyText(String[] wordArray, int maxWidth) {
        List<String> formattedLines = new ArrayList<>();
        int pointer = 0;
        int totalWords = wordArray.length;

        while (pointer < totalWords) {
            int lineStart = pointer;
            int currentChars = 0;

            while (pointer < totalWords && 
                   currentChars + wordArray[pointer].length() + (pointer - lineStart) <= maxWidth) {
                currentChars += wordArray[pointer].length();
                pointer++;
            }

            boolean isFinalLine = (pointer == totalWords);
            int wordsInLine = pointer - lineStart;
            int spacesNeeded = maxWidth - currentChars;
            
            StringBuilder line = new StringBuilder();
            
            if (isFinalLine || wordsInLine == 1) {
                for (int w = lineStart; w < pointer; w++) {
                    line.append(wordArray[w]).append(" ");
                }
                line.setLength(maxWidth);
            } else {
                int gapCount = wordsInLine - 1;
                int baseSpaces = spacesNeeded / gapCount;
                int extraSpaces = spacesNeeded % gapCount;
                
                for (int w = lineStart; w < pointer - 1; w++) {
                    line.append(wordArray[w]);
                    int spacesToAdd = baseSpaces + (w - lineStart < extraSpaces ? 1 : 0);
                    for (int s = 0; s < spacesToAdd; s++) line.append(' ');
                }
                line.append(wordArray[pointer - 1]);
            }
            formattedLines.add(line.toString());
        }
        return formattedLines;
    }
}

Valid Palindrome

A string qualifies as a palindrome if it reads identically forward and backward after ignoring non-alphanumeric characters and case sensitivity. This can be solved efficiently by filtering the input into a normalized buffer or using a bidirectional pointer sweep that skips invalid characters on the fly.

Is Subsequence

Unlike a substring, a subsequence maintains character order but allows for gaps. A greedy two-pointer strategy efficiently verifies if one string is embedded within another by advancing through the target string and matching characters sequentially.

Two Sum II - Input Array Is Sorted

Given an ascending array, the search space can be drastically reduced using bidirectional pointers. By starting at opposite ends and comparing the sum against the target, we eliminate half the possibilities at each step: increment the left pointer if the sum is too small, or decrement the right pointer if it exceeds the target.

Container With Most Water

The capacity of a container formed by vertical lines is calculated as width * min(height[left], height[right]). To maximize the area, the pointer pointing to the shorter line must be moved inward. Shifting the taller line never increases the minimum height and strictly reduces the width, guaranteeing a smaller or equal area.

3Sum

Finding triplets that sum to zero requires sorting the array first. For each element treated as an anchor, the problem reduces to a two-sum search on the remaining subarray. Careful duplicate skipping is necessary to ensure unique combinations.

public class TripleSumFinder {
    public List<List<Integer>> findZeroSumTriplets(int[] data) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(data);
        int length = data.length;

        for (int anchor = 0; anchor < length - 2; anchor++) {
            if (anchor > 0 && data[anchor] == data[anchor - 1]) continue;
            
            int leftBoundary = anchor + 1;
            int rightBoundary = length - 1;
            
            while (leftBoundary < rightBoundary) {
                int currentSum = data[anchor] + data[leftBoundary] + data[rightBoundary];
                
                if (currentSum == 0) {
                    result.add(Arrays.asList(data[anchor], data[leftBoundary], data[rightBoundary]));
                    while (leftBoundary < rightBoundary && data[leftBoundary] == data[leftBoundary + 1]) leftBoundary++;
                    while (leftBoundary < rightBoundary && data[rightBoundary] == data[rightBoundary - 1]) rightBoundary--;
                    leftBoundary++;
                    rightBoundary--;
                } else if (currentSum < 0) {
                    leftBoundary++;
                } else {
                    rightBoundary--;
                }
            }
        }
        return result;
    }
}

Minimum Size Subarray Sum

A sliding window approach solves this by expanding the right boundary until the cumulative sum meets the requirement, then contracting the left boundary to minimize the window size. If no valid subarray exists after scanning the entire array, the result defaults to zero.

public class SubarrayAnalyzer {
    public int calculateMinimalLength(int threshold, int[] sequence) {
        int shortestLength = Integer.MAX_VALUE;
        int currentTotal = 0;
        int leftEdge = 0;

        for (int rightEdge = 0; rightEdge < sequence.length; rightEdge++) {
            currentTotal += sequence[rightEdge];
            
            while (currentTotal >= threshold) {
                int windowSpan = rightEdge - leftEdge + 1;
                shortestLength = Math.min(shortestLength, windowSpan);
                currentTotal -= sequence[leftEdge++];
            }
        }
        
        return shortestLength == Integer.MAX_VALUE ? 0 : shortestLength;
    }
}

Longest Substring Without Repeating Characters

Maintain a dynamic window tracking unique characters. When a duplicate is encountered, the left boundary jumps past the previous occurrence of that character. A hash map storing the latest index of each character enables O(1) lookups and immediate boundary adjustments.

public class SubstringTracker {
    public int measureLongestUnique(String text) {
        Map<Character, Integer> lastSeenPositions = new HashMap<>();
        int maxLength = 0;
        int windowStart = 0;

        for (int currentIndex = 0; currentIndex < text.length(); currentIndex++) {
            char currentChar = text.charAt(currentIndex);
            
            if (lastSeenPositions.containsKey(currentChar)) {
                windowStart = Math.max(windowStart, lastSeenPositions.get(currentChar) + 1);
            }
            
            lastSeenPositions.put(currentChar, currentIndex);
            maxLength = Math.max(maxLength, currentIndex - windowStart + 1);
        }
        return maxLength;
    }
}

Substring with Concatenation of All Words

This problem involves locating substrings composed of a specific set of words with identical lengths. By iterating through the string and extracting fixed-length segments, we can compare the frequency distribution of extracted words against the target dictionary using hash maps.

public class WordSequenceFinder {
    public List<Integer> locateConcatenatedIndices(String source, String[] dictionary) {
        List<Integer> matchIndices = new ArrayList<>();
        if (source == null || dictionary.length == 0) return matchIndices;

        int singleWordLen = dictionary[0].length();
        int totalWordCount = dictionary.length;
        int segmentLength = singleWordLen * totalWordCount;

        Map<String, Integer> requiredFreq = new HashMap<>();
        for (String word : dictionary) {
            requiredFreq.merge(word, 1, Integer::sum);
        }

        for (int startPos = 0; startPos <= source.length() - segmentLength; startPos++) {
            Map<String, Integer> observedFreq = new HashMap<>();
            boolean isValid = true;

            for (int offset = 0; offset < totalWordCount; offset++) {
                int wordStart = startPos + (offset * singleWordLen);
                String extractedWord = source.substring(wordStart, wordStart + singleWordLen);

                if (!requiredFreq.containsKey(extractedWord)) {
                    isValid = false;
                    break;
                }
                
                observedFreq.merge(extractedWord, 1, Integer::sum);
                if (observedFreq.get(extractedWord) > requiredFreq.get(extractedWord)) {
                    isValid = false;
                    break;
                }
            }
            
            if (isValid) matchIndices.add(startPos);
        }
        return matchIndices;
    }
}