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.