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

---

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

---

Merge Strings Alternately (LeetCode 1768)

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"

---

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'

---

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.

---

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"

---

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"

---

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.

---

Longest Palindromic Substring (LeetCode 5)

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = expandAroundCenter(s, i, i);
            int even = expandAroundCenter(s, i, i + 1);
            int max_len = Math.max(odd, even);

            if (max_len > end - start) {
                start = i - (max_len - 1) / 2;
                end = i + max_len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        start = end = 0
        for i in range(len(s)):
            odd = expand(i, i)
            even = expand(i, i + 1)
            max_len = max(odd, even)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
        return s[start:end + 1]

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

• Approach: Expand Around Center. For each index, expand outward for both odd-length and even-length palindromes. Track the longest found.
• Dry run (s = "babad"):
  • i=0: odd=1 ("b"), even=0. max_len=1.
  • i=1: odd=3 ("aba"), even=0. max_len=3. start=0, end=2.
  • i=2: odd=3 ("bab"), even=0. max_len=3. No update (3 == 3-0).
  • i=3: odd=1, even=0.
  • i=4: odd=1, even=0.
  • Result: s[0:3] = "bab"

---

Frequency of Character (uppercase) (GeeksforGeeks)

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

---

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

---

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.

---

Find Words That Can Be Formed by Characters (LeetCode 1160)

1160. Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once for each word in words).
Return the sum of lengths of all good strings in words.

Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

class Solution {
    int f[] = new int[26];
    public int countCharacters(String[] words, String chars) {
        for (char c : chars.toCharArray()) {
            f[c - 'a']++;
        }
        int r=0;
        for(String w:words){
            if(poss(w)) r+=w.length();
        }
        return r;
    }
    public boolean poss(String r) {
        int temp[] = f.clone();
        for (char c : r.toCharArray()) {
            if (temp[c - 'a'] == 0)
                return false;
            temp[c - 'a']--;
        }
        return true;
    }
}

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        from collections import Counter
        char_count = Counter(chars)
        res = 0
        for word in words:
            word_count = Counter(word)
            if all(word_count[c] <= char_count[c] for c in word_count):
                res += len(word)
        return res

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

• Approach: Count the frequency of each character in chars. For each word, check if its character frequencies are less than or equal to those in chars. If so, add the word's length to the total.
• Dry run (words = ["cat","bt","hat","tree"], chars = "atach"):
  • chars counts: {a:2, t:1, c:1, h:1}
  • "cat" counts: {c:1, a:1, t:1} <= chars counts -> good, res = 3
  • "bt" counts: {b:1, t:1} -> 'b' not in chars -> bad
  • "hat" counts: {h:1, a:1, t:1} <= chars counts -> good, res = 6
  • "tree" counts: {t:1, r:1, e:2} -> 'r', 'e' not in chars -> bad
  • Return 6

---

Rearrange Characters to Make Target String (LeetCode 2287)

2287. Rearrange Characters to Make Target String

You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.
Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.

Example 1:
Input: s = "ilovecodingonleetcode", target = "code"
Output: 2
Explanation:
For the first copy of "code", take the letters at indices 4, 5, 6, and 7.
For the second copy of "code", take the letters at indices 17, 18, 19, and 20.
The strings that are formed are "ecod" and "code" which can both be rearranged into "code".
We can make at most two copies of "code", so we return 2.

Example 2:
Input: s = "abcba", target = "abc"
Output: 1
Explanation:
We can make one copy of "abc" by taking the letters at indices 0, 1, and 2.
We can make at most one copy of "abc", so we return 1.
Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".

Example 3:
Input: s = "abbaccaddaeea", target = "aaaaa"
Output: 1
Explanation:
We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12.
We can make at most one copy of "aaaaa", so we return 1.

class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] sf=new int[26];
        int[] tf=new int[26];
        int count=Integer.MAX_VALUE;
        for(char c:s.toCharArray()){
            sf[c-'a']++;
        }
        for(char c:target.toCharArray()){
            tf[c-'a']++;
        }
        for(char c:target.toCharArray()){
            count=Math.min(count,(sf[c-'a']/tf[c-'a']));
        }
        return count;
    }
}

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        sf = [0] * 26
        tf = [0] * 26
        for c in s:
            sf[ord(c) - ord('a')] += 1
        for c in target:
            tf[ord(c) - ord('a')] += 1

        ans = float('inf')
        for c in target:
            idx = ord(c) - ord('a')
            ans = min(ans, sf[idx] // tf[idx])
        return ans

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

• Approach: Count the frequencies of all characters in string s and the target string. For each character in the target, divide its frequency in s by its frequency in target to find how many copies can be formed. The minimum ratio across all target characters is the answer.
• Dry run (s = "ilovecodingonleetcode", target = "code"):
  • s count for 'c': 2, target count for 'c': 1 -> 2 // 1 = 2
  • s count for 'o': 4, target count for 'o': 1 -> 4 // 1 = 4
  • s count for 'd': 2, target count for 'd': 1 -> 2 // 1 = 2
  • s count for 'e': 4, target count for 'e': 1 -> 4 // 1 = 4
  • Minimum is 2.

---

Is Subsequence (LeetCode 392)

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.

---

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.

---

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

---

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

---

Add Strings (LeetCode 415)

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"

---

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"

---

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

---