Reverse String (LeetCode 344)

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++; right--;
        }
    }
}

class Solution:
    def reverseString(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

Type	Value
Time	O(n)
Space	O(1)

• Dry run (s = [h,e,l,l,o]):
  • swap 0↔4 → [o,e,l,l,h]
  • swap 1↔3 → [o,l,l,e,h]
  • left=2,right=2 → stop → [o,l,l,e,h]

---

Length of Last Word (LeetCode 58)

58. Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

Example 1:
Input: s = "Hello World"
Output: 5

Example 2:
Input: s = " fly me to the moon "
Output: 4

class Solution {
    public int lengthOfLastWord(String s) {
        String[] words = s.trim().split(" ");
        return words[words.length - 1].length();
    }
}

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        words = s.split()
        return len(words[-1])

Type	Value
Time	O(n)
Space	O(n)

• Dry run ("Hello World "):
  • trim → "Hello World"
  • split → ["Hello","World"] → last="World" → len=5

---

Longest Substring Without Repeating Characters (LeetCode 3)

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters.
Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

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.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0;
        int n = s.length() ;
        int m = 0;
        HashSet<Character> set = new HashSet<>();
        while (r < n) {
            char c = s.charAt(r);
            while (set.contains(c)) {
                set.remove(s.charAt(l));
                l++;
            }
            set.add(c);
            m = Math.max(m, r - l + 1);
            r++;
        }
        return m;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = r = 0
        n = len(s)
        m = 0
        seen = set()
        while r < n:
            c = s[r]
            while c in seen:
                seen.remove(s[l])
                l += 1
            seen.add(c)
            m = max(m, r - l + 1)
            r += 1
        return m

Type	Value
Time	O(n)
Space	O(k)

• Approach: Sliding window with HashSet. Expand right pointer, shrink left when duplicate found. k = size of character set.
• Dry run (s = "abcabcbb"):
  • r=0: add 'a', set={a}, m=1
  • r=1: add 'b', set={a,b}, m=2
  • r=2: add 'c', set={a,b,c}, m=3
  • r=3: 'a' in set, remove 'a', l=1, add 'a', set={b,c,a}, m=3
  • r=4: 'b' in set, remove 'b', l=2, add 'b', set={c,a,b}, m=3
  • Continue... final m=3

---

Variant: Return the Actual Substring

class Solution {
    public String longestSubstring(String s) {
        int l = 0, r = 0;
        int n = s.length();
        int maxLen = 0;
        int start = 0;  // track start of best substring
        HashSet<Character> set = new HashSet<>();
        while (r < n) {
            char c = s.charAt(r);
            while (set.contains(c)) {
                set.remove(s.charAt(l));
                l++;
            }
            set.add(c);
            if (r - l + 1 > maxLen) {
                maxLen = r - l + 1;
                start = l;   // store start index
            }
            r++;
        }
        return s.substring(start, start + maxLen);
    }
}

class Solution:
    def longestSubstring(self, s: str) -> str:
        l = r = 0
        n = len(s)
        max_len = 0
        start = 0
        seen = set()
        while r < n:
            c = s[r]
            while c in seen:
                seen.remove(s[l])
                l += 1
            seen.add(c)
            if r - l + 1 > max_len:
                max_len = r - l + 1
                start = l
            r += 1
        return s[start:start + max_len]

Type	Value
Time	O(n)
Space	O(k)

• Dry run (s = "abcabcbb"):
  • Same as above, but tracks start index when maxLen updates
  • Final: start=0, maxLen=3 → return "abc"

---

Roman to Integer (LeetCode 13)

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Given a roman numeral, convert it to an integer.

Example 1:
Input: s = "III"
Output: 3

Example 2:
Input: s = "LVIII"
Output: 58

Example 3:
Input: s = "MCMXCIV"
Output: 1994

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int num = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            switch (s.charAt(i)) {
                case 'I': num = 1; break;
                case 'V': num = 5; break;
                case 'X': num = 10; break;
                case 'L': num = 50; break;
                case 'C': num = 100; break;
                case 'D': num = 500; break;
                case 'M': num = 1000; break;
            }
            if (num * 4 < sum) sum -= num; else sum += num;
        }
        return sum;
    }
}

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        total = 0
        for i in range(len(s) - 1, -1, -1):
            num = roman_map[s[i]]
            if num * 4 < total:
                total -= num
            else:
                total += num
        return total

Type	Value
Time	O(n)
Space	O(1)

• Dry run ("MCMXCIV") from right:
  • V(5) → sum=5
  • I(1): 1*4<5 → sum=4
  • C(100): 100*4<4? no → sum=104
  • X(10): 10*4<104 → sum=94
  • M(1000): add → 1094
  • C(100): subtract → 994
  • M(1000): add → 1994

---

Integer to Roman (Leetcode 12)

12. Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

Given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
900 = CM
90 = XC
4 = IV

class Solution {

    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(symbols[i]);
                num -= values[i];
            }
        }
        return result.toString();
    }
}

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        res = []
        for v, sym in zip(values, symbols):
            while num >= v:
                res.append(sym)
                num -= v
        return "".join(res)

Type	Value
Time	O(n)
Space	O(1)

• Approach: Use greedy matching. Iterate through value-symbol pairs from largest to smallest, appending symbols while the number allows.
• Dry run (num = 1994):
  • 1994 >= 1000 → "M", num=994
  • 994 >= 900 → "MCM", num=94
  • 94 >= 90 → "MCMXC", num=4
  • 4 >= 4 → "MCMXCIV", num=0
  • Result: "MCMXCIV"

---

Anagram (LeetCode 242)

242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
            freq[t.charAt(i) - 'a']--;
        }
        for (int count : freq) if (count != 0) return false;
        return true;
    }
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        freq = [0] * 26
        for c1, c2 in zip(s, t):
            freq[ord(c1) - ord('a')] += 1
            freq[ord(c2) - ord('a')] -= 1
        return all(count == 0 for count in freq)

Type	Value
Time	O(n)
Space	O(1)

• Dry run (s="ab", t="ba"):
  • i=0: freq[a]++ →1; freq[b]-- →-1
  • i=1: freq[b]++ →0; freq[a]-- →0
  • All zeros → true

---

Frequency of Character (uppercase)

GeeksforGeeks

Given a string s consisting of uppercase alphabetic characters, print the frequency of each character in alphabetical order.

Example 1:
Input: s = "SURYAS"
Output: A 1, R 1, S 2, U 1, Y 1

class Main {
    public static void main(String[] args) {
        String s = "SURYAS";
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'A']++;
        }
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                System.out.println((char)(i + 'A') + " " + freq[i]);
            }
        }
    }
}

class Main:
    def main(self):
        s = "SURYAS"
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('A')] += 1

        for i, count in enumerate(freq):
            if count > 0:
                print(f"{chr(i + ord('A'))} {count}")

Type	Value
Time	O(n)
Space	O(1)

• Dry run:
  • S→ index 18 → freq[18]=1
  • U→ 20 → 1
  • R→ 17 → 1
  • Y→ 24 → 1
  • A→ 0 → 1
  • S→ 18 → 2
  • Output in alphabetical order: A 1, R 1, S 2, U 1, Y 1

---

Valid palindrome (LeetCode 125)

125. Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

class Solution {

    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) {
                l++;
            }
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) {
                r--;
            }
            if (Character.toLowerCase(s.charAt(l)) !=
                Character.toLowerCase(s.charAt(r))) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Type	Value
Time	O(n)
Space	O(1)

• Dry run (s = "A man, a plan, a canal: Panama"):
  • Pointers start at ends. l=0 ('A'), r=29 ('a'). Match (ignore case) -> l=1, r=28
  • Skip non-alphanumeric. l=1 (' ') -> l=2.
  • Characters continue matching inward. Result is returning true.

---

Valid Palindrome II (LeetCode 680)

680. Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return isPalindrome(s, left + 1, right) ||
                        isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    private static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check_palindrome(s, i, j):
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return check_palindrome(s, left, right - 1) or check_palindrome(s, left + 1, right)
            left += 1
            right -= 1
        return True

Type	Value
Time	O(n)
Space	O(1)

• Approach: Two pointers from both ends. When mismatch found, try skipping either left or right character and check if remaining is palindrome.
• Dry run (s = "abca"):
  • left=0 ('a'), right=3 ('a') → match, move inward
  • left=1 ('b'), right=2 ('c') → mismatch
  • Try isPalindrome(s, 2, 2) "c" → true
  • Return true (can delete 'b')

---

Variant: Return the Palindrome String

public class PalindromeFix {

    public static String makePalindrome(String s) {
        int left = 0, right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                if (isPalindrome(s, left + 1, right)) {
                    return s.substring(0, left) + s.substring(left + 1);
                }

                if (isPalindrome(s, left, right - 1)) {
                    return s.substring(0, right) + s.substring(right + 1);
                }

                return "Not possible";
            }
            left++;
            right--;
        }

        return s;
    }

    public static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(makePalindrome("malayala")); // malayalam
        System.out.println(makePalindrome("abcddcb"));  // abcddc
        System.out.println(makePalindrome("racecar"));  // racecar
    }
}

class PalindromeFix:
    def makePalindrome(self, s: str) -> str:
        def check_palindrome(s, i, j):
            while i < j:
                if s[i] != s[j]:
                     return False
                i += 1
                j -= 1
            return True

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                if check_palindrome(s, left + 1, right):
                    return s[:left] + s[left+1:]
                if check_palindrome(s, left, right - 1):
                    return s[:right] + s[right+1:]
                return "Not possible"
            left += 1
            right -= 1
        return s

Type	Value
Time	O(n)
Space	O(n)

• Approach: Similar to Valid Palindrome II, but returns the actual palindrome string after removing one character.
• Dry run (s = "abcddcb"):
  • left=0 ('a'), right=6 ('b') → mismatch
  • isPalindrome(s, 1, 6) "bcddcb" → true
  • Return s[0..0] + s[1..] = "" + "bcddcb" = "bcddcb"

---

Check if Binary String Has at Most One Segment of Ones (LeetCode 1784)

1784. Check if Binary String Has at Most One Segment of Ones

Given a binary string s ​​​​​without leading zeros, return true​​​ if s *contains at most one contiguous segment of ones*. Otherwise, return false.

Example 1:

Input: s = "1001"
Output: false
Explanation: The ones do not form a contiguous segment.

Example 2:

Input: s = "110"
Output: true

class Solution {
    public boolean checkOnesSegment(String s) {
      if(s.contains("01")){
         return false;
      }
      return true;
    }
}

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        return "01" not in s

Type	Value
Time	O(n)
Space	O(1)

• Dry run (s = "1001"):
  • Call s.contains("01")
  • "1001" contains "01" -> returns true from .contains, so we return false
  • Returns false as expected because 1s are not one segment.

---

String to Integer (Leetcode 8)

8. String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

1. Whitespace: Ignore any leading whitespace (" ").
2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present.
3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

class Solution {
    public int myAtoi(String s) {
        s = s.trim();
        int sign = 1;
        int i = 0;
        long n = 0;
        if (s.isEmpty())
            return 0;
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            sign = (s.charAt(i) == '-' ? -1 : 1);
            i++;
        }
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            n = n * 10 + (s.charAt(i) - '0');
            i++;
            if (sign * n > Integer.MAX_VALUE)
                return Integer.MAX_VALUE;
            if (sign * n < Integer.MIN_VALUE)
                return Integer.MIN_VALUE;
        }
        return (int) (sign * n);
    }
}

class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.strip()
        if not s:
            return 0

        sign = 1
        i = 0
        n = 0

        if s[i] in ['+', '-']:
            if s[i] == '-':
                sign = -1
            i += 1

        while i < len(s) and s[i].isdigit():
            n = n * 10 + int(s[i])
            i += 1

            if sign * n > 2**31 - 1:
                return 2**31 - 1
            if sign * n < -2**31:
                return -2**31

        return sign * n

Type	Value
Time	O(n)
Space	O(1)

• Approach: Iteratively clean up whitespace, determine the sign, and read characters as long as they are digits. Accumulate the number step by step, and check for 32-bit integer overflow or underflow constraints to clamp the result if necessary.
• Dry run (s = " -42"):
  • s.trim() -> "-42"
  • First char is '-', set sign=-1, i=1
  • i=1, char='4', n=0 * 10 + 4 = 4
  • i=2, char='2', n=4 * 10 + 2 = 42
  • return sign * n = -42

---

Palindromic Substrings (Leetcode 647)

647. Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

class Solution {
    int count = 0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length(); i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return count;
    }

    public void expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
    }
}

class Solution:
    def countSubstrings(self, s: str) -> int:
        self.count = 0

        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                self.count += 1
                left -= 1
                right += 1

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)

        return self.count

Type	Value
Time	O(n²)
Space	O(1)

• Approach: Expand Around Center. For each index, expand outward for both odd-length (center=i) and even-length (center=i,i+1) palindromes.
• Dry run (s = "aaa"):
  • i=0: odd expand(0,0) → "a" (count=1). even expand(0,1) → "aa" (count=2).
  • i=1: odd expand(1,1) → "a","aaa" (count=4). even expand(1,2) → "aa" (count=5).
  • i=2: odd expand(2,2) → "a" (count=6). even expand(2,3) → stop.
  • Total = 6.

---

Word Break (LeetCode 139)

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;

        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){

                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break

        return dp[len(s)]

Type	Value
Time	O(n²)
Space	O(n)

• Approach: Use DP. dp[i] is true if s[0..i-1] can be segmented. For each position i, check all substrings s[j..i] — if dp[j] is true and substring is in dict, set dp[i] = true.
• Dry run (s = "leetcode", wordDict = ["leet","code"]):
  • dp[0]=true
  • i=4: j=0, dp[0]=true, s[0..4]="leet" in dict → dp[4]=true
  • i=8: j=4, dp[4]=true, s[4..8]="code" in dict → dp[8]=true
  • Return dp[8] = true

---

---

Isomorphic Strings (LeetCode 205)

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"

Output: true

Explanation:

The strings s and t can be made identical by:

• Mapping 'e' to 'a'.
• Mapping 'g' to 'd'.

Example 2:

Input: s = "f11", t = "b23"

Output: false

Explanation:

The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.

class Solution {

    public boolean isIsomorphic(String s, String t) {
        int[] mapS = new int[256];
        int[] mapT = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);
            if (mapS[charS] != mapT[charT]) {
                return false;
            }
            mapS[charS] = i + 1;
            mapT[charT] = i + 1;
        }
        return true;
    }
}

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        map_s = {}
        map_t = {}
        for i, (c1, c2) in enumerate(zip(s, t)):
            if map_s.get(c1, -1) != map_t.get(c2, -1):
                return False
            map_s[c1] = i + 1
            map_t[c2] = i + 1
        return True

Type	Value
Time	O(n)
Space	O(1)

• Approach: Use two arrays to map characters to their most recent positions (1-indexed). If a mismatched previous mapping is found, they are not isomorphic.
• Dry run (s="egg", t="add"):
  • i=0 ('e', 'a'): mapS['e']=mapT['a']=0. Both become 1.
  • i=1 ('g', 'd'): mapS['g']=mapT['d']=0. Both become 2.
  • i=2 ('g', 'd'): mapS['g']=mapT['d']=2 (match). Both become 3.
  • Returns true.

---

Word Break (LeetCode 139) - Alternative format

139. Word Break

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[len(s)]

Type	Value
Time	O(n²)
Space	O(n)

• Approach: Use DP array where dp[i] indicates if substring 0..i can be broken down.
• Dry run (s = "leetcode", wordDict = ["leet","code"]):
  • dp[0]=true.
  • i=4, j=0: s[0..4] is "leet", in dict. dp[4]=true.
  • i=8, j=4: s[4..8] is "code", in dict. dp[8]=true.
  • Return dp[8] = true.

---

String Reverse (GeeksforGeeks)

Reverse a String

Given a string, print it in reverse order.

Example 1:
Input: s = "surya"
Output: ayrus

public class Main {
    public static void main(String[] args) {
        String s = "surya";
        int n = s.length();

        for (int i = 0; i < n; i++) {
            System.out.print(s.charAt(n - i - 1));
        }
    }
}

class Main:
    def main(self):
        s = "surya"
        n = len(s)
        for i in range(n):
            print(s[n - i - 1], end="")
        print()

Type	Value
Time	O(n)
Space	O(1)

• Approach: Loop from 0 to n-1 and print characters starting from the end of the string.
• Dry run (s="surya"):
  • i=0: print s.charAt(4) -> 'a'
  • i=1: print s.charAt(3) -> 'y'
  • i=2: print s.charAt(2) -> 'r'
  • i=3: print s.charAt(1) -> 'u'
  • i=4: print s.charAt(0) -> 's'
  • Result: ayrus

---

Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return isPalindrome(s, left + 1, right) ||
                        isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    private static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}

---

Add Strings

415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int d1 = (i >= 0) ? num1.charAt(i) - '0' : 0;
            int d2 = (j >= 0) ? num2.charAt(j) - '0' : 0;
            int sum = d1 + d2 + carry;
            result.append(sum % 10);
            carry = sum / 10;
            i--;
            j--;
        }
        return result.reverse().toString();
    }
}

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        carry, res = 0, []
        while i >= 0 or j >= 0 or carry:
            d1 = int(num1[i]) if i >= 0 else 0
            d2 = int(num2[j]) if j >= 0 else 0
            total = d1 + d2 + carry
            res.append(str(total % 10))
            carry = total // 10
            i, j = i - 1, j - 1
        return "".join(res[::-1])

Type	Value
Time	O(max(N, M))
Space	O(max(N, M))

• Approach: Simulate grade-school addition starting from least significant digit.
• Dry run (num1="11", num2="123"):
  • 1+3 -> 4, carry=0
  • 1+2 -> 3, carry=0
  • 0+1 -> 1, carry=0
  • Result "134"

---

Merge Strings Alternately

1768. Merge Strings Alternately

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r

Example 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s

Example 3:

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d

class Solution {

    public String mergeAlternately(String w1, String w2) {
        int i=0;
        StringBuilder s=new StringBuilder();
        while(i<w1.length() || i<w2.length()){
                if(i<w1.length()){
                    s.append(w1.charAt(i));
                }
                if(i<w2.length()){
                    s.append(w2.charAt(i));
                }
                i++;
        }
        return s.toString();
    }
}

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        res = []
        i, j = 0, 0
        while i < len(word1) or j < len(word2):
            if i < len(word1):
                res.append(word1[i])
                i += 1
            if j < len(word2):
                res.append(word2[j])
                j += 1
        return "".join(res)

Type	Value
Time	O(N + M)
Space	O(N + M)

• Approach: Use loop for indices and append alternately.
• Dry run (word1="abc", word2="pq"):
  • a, p
  • b, q
  • c
  • Result: "apbqc"

---

Is Subsequence

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

class Solution {

    public boolean isSubsequence(String s, String t) {

        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

Type	Value
Time	O(N)
Space	O(1)

• Approach: Two pointers tracking characters matched.
• Dry run (s="abc", t="ahbgdc"):
  • 'a' == 'a' -> i=1, j=1
  • 'b' no -> j=2
  • 'b' == 'b' -> i=2, j=3
  • 'c' no -> j=4
  • 'c' == 'c' -> i=3, j=5 -> return true.

---

First Letter to Appear Twice (LeetCode 2351)

2351. First Letter to Appear Twice

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Example 1:
Input: s = "abccbaacz"
Output: "c"

Example 2:
Input: s = "abcdd"
Output: "d"

import java.util.*;
class Solution {
    public char repeatedCharacter(String s) {
        HashSet<Character> seen = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (seen.contains(c)) return c;
            seen.add(c);
        }
        return 'a';
    }
}

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        seen = set()
        for c in s:
            if c in seen:
                return c
            seen.add(c)
        return 'a'

Type	Value
Time	O(n)
Space	O(1)

• Approach: Use a HashSet to track seen characters. Return the first one that is already in the set. Space is O(1) as there are at most 26 lowercase English letters.
• Dry run (s="abccbaacz"):
  • 'a' -> seen={'a'}
  • 'b' -> seen={'a','b'}
  • 'c' -> seen={'a','b','c'}
  • 'c' -> in seen! Return 'c'

---

Lexicographically Smallest Palindrome (LeetCode 2697)

2697. Lexicographically Smallest Palindrome

You are given a string s consisting of lowercase English letters. Make s a palindrome with the minimum number of operations. If there are multiple palindromes that can be made using the minimum operations, make the lexicographically smallest one. Return the resulting palindrome string.

Example 1:
Input: s = "egcfe"
Output: "efcfe"

Example 2:
Input: s = "abcd"
Output: "abba"

class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] c = s.toCharArray();
        int l = 0, r = c.length - 1;
        while (l < r) {
            if (c[l] != c[r]) {
                char minChar = (char) Math.min(c[l], c[r]);
                c[l] = minChar;
                c[r] = minChar;
            }
            l++;
            r--;
        }
        return new String(c);
    }
}

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        chars = list(s)
        left, right = 0, len(chars) - 1
        while left < right:
            if chars[left] != chars[right]:
                min_char = min(chars[left], chars[right])
                chars[left] = chars[right] = min_char
            left += 1
            right -= 1
        return "".join(chars)

Type	Value
Time	O(n)
Space	O(n)

• Approach: Two pointers approach. When s[l] != s[r], replace both with the lexicographically smaller character to achieve the minimum number of operations towards the lexicographically smallest palindrome.
• Dry run (s="egcfe"):
  • l=0, r=4: 'e' == 'e'
  • l=1, r=3: 'g' != 'f', replace both with 'f'
  • Result: "efcfe"

Excel Sheet Column Title (LeetCode 168)

168. Excel Sheet Column Title

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

Example 1:
Input: columnNumber = 1
Output: "A"

Example 2:
Input: columnNumber = 28
Output: "AB"

Example 3:
Input: columnNumber = 701
Output: "ZY"

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber > 0) {
            columnNumber--;
            int rem = columnNumber % 26;
            char ch = (char) ('A' + rem);
            sb.append(ch);
            columnNumber /= 26;
        }
        return sb.reverse().toString();
    }
}

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        res = []
        while columnNumber > 0:
            columnNumber -= 1
            rem = columnNumber % 26
            res.append(chr(ord('A') + rem))
            columnNumber //= 26
        return "".join(res[::-1])

Type	Value
Time	O(log n)
Space	O(1)

• Approach: Repeatedly subtract 1 (since Excel columns are 1-indexed, not 0-indexed), then modulo by 26 to find the character from 'A' to 'Z', and integer divide by 26.
• Dry run (columnNumber = 28):
  • n=27, rem=1 ('B'), append 'B', n=1
  • n=0, rem=0 ('A'), append 'A', n=0
  • Reverse "BA" -> "AB"

Excel Sheet Column Number (LeetCode 171)

171. Excel Sheet Column Number

Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

Example 1:
Input: columnTitle = "AB"
Output: 28

Example 2:
Input: columnTitle = "ZY"
Output: 701

class Solution {
    public int titleToNumber(String columnTitle) {
        int result = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            result = result * 26 + (columnTitle.charAt(i) - 'A' + 1);
        }
        return result;
    }
}

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        r = 0
        for i in columnTitle:
            r = r * 26 + (ord(i) - ord('A') + 1)
        return r

Type	Value
Time	O(n)
Space	O(1)

• Approach: Iterate through the string from left to right. Just like converting from base 10 (or binary base 2) to decimal, here we convert from a base 26 system to decimal. At each character, multiply the current result by 26 and add the current character's integer value ('A' -> 1).
• Dry run (columnTitle="AB"):
  • char 'A' -> val=1 -> result = 0*26 + 1 = 1
  • char 'B' -> val=2 -> result = 1*26 + 2 = 28
  • Result: 28