Basic Strings
Reverse a String II
class Solution {
public void reverseString(List<Character> s) {
int n = s.size();
for (int i = 0, j = n - 1; i < j; ++i, --j) {
Character temp = s.get(i);
s.set(i, s.get(j));
s.set(j, temp);
}
return;
}
}This is an iterative in-place reversal of a list of characters using a two-pointer approach. One pointer starts at the beginning and the other at the end. They move towards the center, swapping elements at each step.
Time Complexity: O(n), where n is the number of characters.
Space Complexity: O(1).
Palindrome Check
class Solution {
public boolean palindromeCheck(String s) {
int start = 0, end = s.length() - 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) return false;
++start;
--end;
}
return true;
}
}The algorithm uses a two-pointer approach to check for a palindrome. The start pointer begins at the first character and the end pointer at the last. It compares the characters at both pointers, moving them towards the center. If a mismatch is found, the string is not a palindrome.
Time Complexity: O(n), as it makes n/2 comparisons in the worst case.
Space Complexity: O(1).
Largest Odd Number in a String
class Solution {
public String largeOddNum(String s) {
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != '0') {
s = s.substring(i, s.length());
break;
}
}
int lastOdd = -1;
for (int i = 0; i < s.length(); ++i) {
if ((s.charAt(i) - '0') % 2 == 1)
lastOdd = i;
}
return s.substring(0, lastOdd + 1);
}
}The goal is to find the largest odd number that is a prefix of the given string. A more optimal approach is to find the rightmost odd digit. The largest odd number is the substring from the beginning up to that rightmost odd digit. The provided code first trims leading zeros and then finds the last odd digit to determine the substring. A cleaner way is to iterate from the end of the string.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for the substring result in the worst case. The operation itself is O(1) extra space.
Longest Common Prefix
class Solution {
public String longestCommonPrefix(String[] str) {
int minLength = (int) 1e9 + 7;;
for (int i = 0; i < str.length; ++i) {
minLength = Math.min(minLength, str[i].length());
}
for (int i = 1; i <= minLength; ++i) {
String candidate = str[0].substring(0, i);
boolean flag = true;
for (int j = 1; j < str.length; ++j) {
if (!str[j].substring(0, i).equals(candidate)) {
flag = false;
break;
}
}
if (!flag) {
return str[0].substring(0, i - 1);
}
}
return str[0].substring(0, minLength);
}
}This method finds the longest common prefix by "horizontal scanning". It assumes the prefix of a certain length from the first string and then checks if this prefix matches the start of all other strings. It does this for all possible prefix lengths, from 1 up to the length of the shortest string in the array.
Time Complexity: O(S), where S is the total number of characters in all strings. In the worst case, where all strings are the same, this is O(k * m) where k is the number of strings and m is the average string length. The given implementation is less optimal, closer to O(k * m^2) where m is the minimum length, due to repeated substring creation and comparison.
Space Complexity: O(m) for the substring candidate.
Isomorphic String
class Solution {
public boolean isomorphicString(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Character> map12 = new HashMap<>();
Map<Character, Character> map21 = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
Character sChar = map12.get(s.charAt(i));
Character tChar = map21.get(t.charAt(i));
if (sChar == null ^ tChar == null) return false;
if (sChar != null) {
if (t.charAt(i) != sChar || s.charAt(i) != tChar) return false;
}
map12.put(s.charAt(i), t.charAt(i));
map21.put(t.charAt(i), s.charAt(i));
}
return true;
}
}Two strings are isomorphic if there is a one-to-one mapping between their characters. The algorithm verifies this by using two hash maps: one to map characters from s to t (map12) and another from t to s (map21). This ensures the mapping is unique in both directions.
Time Complexity: O(n), where n is the length of the strings.
Space Complexity: O(k), where k is the number of unique characters (at most the size of the character set).
Rotate String
class Solution {
public boolean rotateString(String s, String goal) {
if (s.length() != goal.length()) return false;
String temp = s + s;
return temp.contains(goal);
}
}This clever algorithm checks if goal is a rotation of s. It works on the principle that if goal is a rotation of s, then goal must be a substring of s concatenated with itself (s+s).
Time Complexity: O(n), assuming an efficient underlying contains implementation (like KMP). If it's a naive implementation, it could be O(n^2). String concatenation also takes O(n).
Space Complexity: O(n) to store the concatenated string temp.
Valid Anagram
class Solution {
public boolean anagramStrings(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1);
}
for (var freq : map.values()) {
if (freq != 0) return false;
}
return true;
}
}This method checks if two strings are anagrams by counting character frequencies. It uses a hash map to store counts: incrementing for each character in s and decrementing for each character in t. If the strings are anagrams, all character counts in the map will be zero at the end.
Time Complexity: O(n), where n is the length of the strings.
Space Complexity: O(k), where k is the number of unique characters.