Tag Archives: Strings

Find Two Numbers That Sum to a Given Value

Objective

Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.

Observations

  1. We want to find two elements satisfying:
    element1 + element2 = value
  2. We need to find element1 and element2 within the array that satisfy the equation above (if they even exist), but value is known.
  3. We can rearrange this equation as:
    • element1 = value - element2
    • element2 = value - element1
Code
import java.util.*;

class Solution {
		
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value the pair of elements must sum to
	*
	*	@return The distinct pair of VALUES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumValues(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{nums[i], nums[index]};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
	
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value 
	*
	*	@return The distinct pair of INDICES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumIndices(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{i, index};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
}

Permuting a String to Make a Palindrome

Objective

Given a string of characters, determine whether or not some permutation of the string creates a palindrome.

Observations

  1. A palindrome is a word that reads the same forward as it does backward.
  2. We can use a sequence of characters to build a palindrome if either of the following conditions are satisfied:
    • Each character occurs an even number of times.
    • Each character occurs an even number of times except for one character.
Code
import java.util.*;

class Solution {
	/**
	*	@param String s The string to check
	*	@return true if the string can be permuted into a palindrome
	**/
	public static boolean hasPalindromicPermutation(String s) {
		// Create a set to hold unmatched characters
		Set unmatched = new HashSet();
		
		for (int i = 0; i < s.length(); i++) {
			// The current character
			char c = s.charAt(i);
			
			// If the character exists in the set, remove it
			if (unmatched.contains(c)) {
				unmatched.remove(c);
			}
			// Character is unmatched, add it to the set
			else {
				unmatched.add(c);
			}
		}
		
		// For the string to be a palindrome, only 0 or 1 character can be unmatched
		return (unmatched.size() < 2);
	}
}