3. Longest Substring Without Repeating Characters

public class Solution {

 public static int lengthOfLongestSubstring(String s) {

        if (s == null) {

            return 0;

        }

           

        char[] chars = s.toCharArray();

        int longestSoFar = 0;


        HashMap<Character, Integer> numToIdx = new HashMap<Character, Integer>();


        for (int i = 0; i < chars.length; i++) {

            if (!numToIdx.containsKey(chars[i])) {

                numToIdx.put(chars[i], i);

            } else {

                longestSoFar = Math.max(longestSoFar, numToIdx.size());

                i = numToIdx.get(chars[i]);

                numToIdx.clear();

            }

        }


        return Math.max(longestSoFar, numToIdx.size());

    }

}

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

This is a classic recursion problem.

Solution:

• Use an array to store mapping of digits to Strings as seen in the telephone keypad. The mapping would be {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
• If the input String is a digit (2 <= digit <= 9), then we would add each character in the mapped String to the output and return the letter combinations (e.g the letter combinations of 2 are {"a", "b", "c"}
• If there is more than 1 digit in the input, then we would apply the following steps
• Get mapped String "digitLetters" for first character
• Get letter combinations for remaining substring (starting from the 2nd character in input)
• For each letter combination in the combinations for the remaining substring
• For each character c in digitLetters, concatenate c and letter combination
• Add the resulting new letter combination to the output list 

public class Solution {
  String[] digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  
  public List<String> letterCombinations(String digits) {
    List<String> letterCombo = new ArrayList<String>();
    if (digits.length() == 0) {
      return letterCombo;
    }
    
    String digitLetters = digitMap[digits.charAt(0) - '0'];
    if (digits.length() == 1) {
      for (int i = 0; i < digitLetters.length(); i++) {
        letterCombo.add(String.valueOf(digitLetters.charAt(i)));
      }
      return letterCombo;
    } else {
      List<String> subLetterCombo = letterCombinations(digits.substring(1));
      for (String s : subLetterCombo) {
        for (int i = 0;i < digitLetters.length(); i++) {
          letterCombo.add(digitLetters.charAt(i) + s);
        }
      }
      return letterCombo;
    }
  }
}

38. Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Solution:

• An iterative solution is intuitive
• Since we have to generate the n-th sequence for an integer, it is useful to write a helper that takes a String and generates it's count - and - say sequence
• Initialize starting sequence to "1"
• To generate the n-th sequence for a number n, call the helper n - 1 times and keep updating the sequence

public class Solution {
    public String countAndSay(int n) {
        String curSeq = "1";
        
        for (int p = 2; p <= n; p++) {
            curSeq = countAndSayIt(curSeq);
        }
        return curSeq;
    }
    
    private String countAndSayIt(String curSeq) {
        int pos = 0;
        int N = curSeq.length();
        String countAndSaySeq = "";
        
        while (pos < N) {
            char c = curSeq.charAt(pos);
            int freq = 1;
            pos++;
            
            // check if c repeats consecutively and update freq
            while (pos < N && curSeq.charAt(pos) == c) {
                freq++;
                pos++;
            }
            
            countAndSaySeq += (freq + "" + c);
        }
        
        return countAndSaySeq;
    }
}

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:
Ref: http://www.programcreek.com/2012/12/leetcode-word-ladder/

This problem can be solved using BFS. 

• The first step is to create a data structure that can hold a word and the number of steps needed to get to this word from the start word. WordNode is the data structure we'd use here.
• Create a queue of WordNode objects
• Add a node for the start word with number of steps = 1
• While the queue is not empty, poll and check if the removed node is to the end word
• If yes, return the number of steps
• Otherwise, we start a BFS transformation
• BFS:
• In order to generate the transformation sequence or ladder, we know that only one character can be changed at a time
• Therefore, loop over each character of current word and attempt to replace it with each letter in [a,z]. 
• If the transformed word formed by the step above is present in the dictionary,  add a WordNode for the new word to the queue. The number of steps = number of steps for current word + 1
• Remember to reset the replaced character in current word to continue the transformation sequence with the next character in current word
• In this process, if any transformation sequence terminates in end word, we would return the length of the ladder
• If there is no such transformation sequence, we wind up and return 0 per requirements in the question

class WordNode{
    String word;
    int numSteps;
 
    public WordNode(String word, int numSteps){
        this.word = word;
        this.numSteps = numSteps;
    }
}

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Queue<WordNode> queue = new LinkedList<WordNode>();
        queue.add(new WordNode(beginWord, 1));
        
        while (!queue.isEmpty()) {
            WordNode node = queue.poll();
            String currentWord = node.word;
            
            if (currentWord.equals(endWord)) {
                return node.numSteps;
            }
            
            char[] currentWordChars = currentWord.toCharArray();
            
            for (int i = 0; i < currentWordChars.length; i++) {
                for (char c = 'a'; c <= 'z'; c++){
                    char temp = currentWordChars[i];
                    if (currentWordChars[i] != c) {
                        currentWordChars[i] = c;
                    }
                    
                    String newWord = new String(currentWordChars);
                    if (wordDict.contains(newWord)) {
                        queue.add(new WordNode(newWord, node.numSteps + 1));
                        wordDict.remove(newWord);
                    }
                    currentWordChars[i] = temp;
                }
            }
        }
        return 0;
    }
}