Reverse Words in a String

 Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

 

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Solution

class Solution {

public String reverseWords(String s) {

// Remove leading and trailing spaces and then split the words with whitespace regex

String[] str = s.trim().split("\\s+");

StringBuilder sb = new StringBuilder();

// iterate the words in reverse order

for(int i=str.length-1; i>0; i--) {

// append current word and space to output

sb.append(str[i]).append(" ");

}

// append first word to output

sb.append(str[0]);

return sb.toString();

}

}

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest  substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

class Solution {

public int lengthOfLongestSubstring(String s) {

int n = s.length();

int maxLength = 0;

Map<Character, Integer> charMap = new HashMap<>();

int left = 0;

for (int right = 0; right < n; right++) {

if (!charMap.containsKey(s.charAt(right)) || charMap.get(s.charAt(right)) < left) {

charMap.put(s.charAt(right), right);

maxLength = Math.max(maxLength, right - left + 1);

} else {

left = charMap.get(s.charAt(right)) + 1;

charMap.put(s.charAt(right), right);

}

}

return maxLength;

}

}

Group Anagrams

 Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Solution

class Solution {

public List<List<String>> groupAnagrams(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for(String word : strs) {

char[] chars = word.toCharArray();

Arrays.sort(chars);

String sortedWord = new String(chars);

if(!map.containsKey(sortedWord)) {

map.put(sortedWord, new ArrayList<String>());

}

map.get(sortedWord).add(word);

}

return new ArrayList<>(map.values());

}

}

Number of Islands

 

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300

Solution

class Solution {

public void dfs(char[][] grid, int i, int j) {

int nr = grid.length;

int nc = grid[0].length;

if(i<0 || i>=nr || j<0 || j>=nc || grid[i][j]=='0'){

return;

}

grid[i][j]='0';

// check for any connected islands in all 4 directions

dfs(grid, i-1, j); // top

dfs(grid, i+1, j); // bottom

dfs(grid, i, j-1); // left

dfs(grid, i, j+1); // right

}

public int numIslands(char[][] grid) {

int nr = grid.length;

int nc = grid[0].length;

int islandsCount = 0;

for(int i=0; i<nr; i++) {

for(int j=0; j<nc; j++) {

if(grid[i][j]=='1'){

islandsCount++;

dfs(grid, i, j);

}

}

}

return islandsCount;

}

}