1. Check if a String is a Palindrome. 2. Check if One String is a Rotation of Another. 3. Find the First Non-Repeating Character
Given a string, determine if it reads the same forward and backward. Return true for palindromes and false otherwise.
Example 1:
Input: "level"
Output: trueExample 2:
Input: "hello"
Output: falseConstraints:
Use two pointers that start at the beginning and end of the string and move towards the center while comparing characters. Skip no characters, just compare directly because the prompt does not mention ignoring cases or punctuation.
Steps:
Time Complexity: O(n) – each character is inspected at most once.
Space Complexity: O(1) – only a few pointers are stored.
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("level"))
print(is_palindrome("hello"))
print(is_palindrome("a"))
print(is_palindrome("aa"))
print(is_palindrome("abcba"))In the first version, the while loop mirrors how we would check letters manually: compare both ends, move towards the center, and abort as soon as a mismatch appears. The early return keeps the solution fast for non-palindromes. The Pythonic version leverages slicing to reverse the string in one expression, which is concise but uses extra memory to create the reversed copy.
Given a sentence, reverse the order of the words while trimming extra spaces between them.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"Example 2:
Input: " hello world "
Output: "world hello"Constraints:
Split the string into words, reverse the list, and join with a single space. This automatically handles multiple spaces.
Steps:
Time Complexity: O(n) because each character is seen once.
Space Complexity: O(n) for the resulting reordered string.
def reverse_words(sentence: str) -> str:
parts = sentence.split()
parts.reverse()
return ' '.join(
The split method with no arguments automatically handles multiple consecutive spaces and returns only the words. Reversing the list and joining with a single space produces the desired output efficiently.
Given two strings s1 and s2, determine if s2 is a rotation of s1. Rotations move characters from the front to the back without changing order.
Example 1:
Input: s1 = "waterbottle", s2 = "erbottlewat"
Output: trueExample 2:
Input: s1 = "hello", s2 = "llohe"
Output: trueExample 3:
Input: s1 = "abc", s2 = "acb"
Output: falseConstraints:
A rotation must keep the same length and characters. If s2 is inside s1 + s1 (concatenate s1 with itself), then s2 is a rotation.
Steps:
Time Complexity: O(n) expected (depends on substring search).
Space Complexity: O(n) for the doubled string.
def is_rotation(s1: str, s2: str) -> bool:
Given a string, return the index (0-based) of the first character that does not repeat.
If every character appears more than once, return -1.
Input: "parikshub"
Output: 0Explanation:
Input: "aabb"
Output: -1Count occurrences of each character in a first pass, then scan again to find the first character with frequency 1.
Steps:
Time Complexity: O(n)
Space Complexity: O(1) if alphabet is fixed.
from collections import Counter
def first_unique_character(s: str) -> int:
Given a Roman numeral string, convert it to its integer value.
Example 1:
Input: "III"
Output: 3Example 2:
Input: "MCMXCIV"
Output: 1994Constraints:
Roman numerals normally add values left to right, but when a smaller value precedes a larger value we subtract it (e.g., IV = 5 - 1). Traverse the string, comparing each symbol with the next.
Steps:
Time Complexity: O(n)
Space Complexity: O(1)
def roman_to_int(s: str) -> int:
values = {
"I": 1, "V": 5,
The algorithm relies on the subtractive rule: whenever a symbol of smaller value appears before a bigger one, it contributes negatively. By subtracting before larger symbols and adding otherwise, the running total stays accurate. The final addition of the last symbol accounts for the tail character that lacks a right neighbor inside the loop.
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The function should handle leading whitespace, optional signs, and stop at non-digit characters.
Example 1:
Input: "42"
Output: 42Example 2:
Input: " -42"
Output: -42Example 3:
Input: "4193 with words"
Output: 4193Constraints:
Skip leading whitespace, detect the optional sign, then read digits until a non-digit appears. Clamp the result to the 32-bit integer range.
Steps:
Time Complexity: O(n)
Space Complexity: O(1)
def my_atoi(s: str) -> int:
Encrypt a string by replacing each character with its ASCII value in hexadecimal format, followed by the count of consecutive occurrences of that character.
Example 1:
Input: "aaa"
Output: "613" (ASCII of 'a' is 97 in hex = 61, count = 3)Example 2:
Input: "aabb"
Output: "612622" (a: 61 hex, count 2; b: 62 hex, count 2)Constraints:
Traverse the string and group consecutive identical characters. For each group, convert the character's ASCII value to hexadecimal and append the count.
Steps:
Time Complexity: O(n)
Space Complexity: O(n)
def encrypt_string(s: str) -> str:
if not s:
return ""
result =
The algorithm uses run-length encoding combined with hexadecimal ASCII representation. For each group of consecutive identical characters, we convert the character's ASCII value to hexadecimal format (without the '0x' prefix) and append the count of consecutive occurrences. This creates a compact encrypted representation of the string.
Given a string of brackets, find the position where the number of opening brackets '(' equals the number of closing brackets ')' on both sides of that position.
Example 1:
Input: "(()))(()()())))"
Output: 4 (at index 4, left has 2 opening, right has 2 closing)Example 2:
Input: "()"
Output: 1 (at index 1, left has 1 opening, right has 1 closing)Constraints:
Count total closing brackets first, then traverse the string to find the position where opening brackets on the left equal closing brackets on the right.
Steps:
Time Complexity: O(n)
Space Complexity: O(1)
def find_equal_point(s: str) -> int:
total_close = s.count(')')
open_count = 0
close_count = total_close
The solution first counts all closing brackets to know the total. Then it traverses the string, tracking opening brackets on the left and decrementing the closing bracket count as we encounter them. When the opening count equals the remaining closing count, we've found the equal point where both sides have balanced brackets.
Given two strings, determine if they are anagrams of each other. Anagrams are strings that contain the same characters in the same frequency, but possibly in different order.
Example 1:
Input: s1 = "listen", s2 = "silent"
Output: trueExample 2:
Input: s1 = "rat", s2 = "car"
Output: falseExample 3:
Input: s1 = "anagram", s2 = "nagaram"
Output: trueConstraints:
Two strings are anagrams if they have the same character frequencies. Count characters in both strings and compare the frequency maps.
Steps:
Time Complexity: O(n)
Space Complexity: O(1) if alphabet size is fixed
from collections import Counter
def are_anagrams(s1: str, s2: str)
Given a string, reverse it and return the reversed string.
Example 1:
Input: "hello"
Output: "olleh"Example 2:
Input: "Python"
Output: "nohtyP"Example 3:
Input: "a"
Output: "a"Constraints:
Iterate through the string from end to start and build the reversed string.
Steps:
Time Complexity: O(n) - iterate through string once
Space Complexity: O(n) - store reversed string
def reverseString(s):
result = ""
i = len(s)
Given a string, count the number of vowels and consonants in it. Consider only alphabetic characters and ignore case.
Example 1:
Input: "Hello World"
Output: Vowels: 3, Consonants: 7Example 2:
Input: "Programming"
Output: Vowels: 3, Consonants: 8Example 3:
Input: "aeiouAEIOU"
Output: Vowels: 10, Consonants: 0Constraints:
Iterate through each character in the string. Check if it's a letter, then determine if it's a vowel or consonant by comparing against a vowel set.
Steps:
Time Complexity: O(n) – single pass through the string.
Space Complexity: O(1) – fixed vowel set size.
def count_vowels_consonants(s: str)
Given a sentence, count the number of words in it. Words are separated by one or more spaces.
Example 1:
Input: "Hello World"
Output: 2Example 2:
Input: " The quick brown fox "
Output: 4Example 3:
Input: "SingleWord"
Output: 1Constraints:
Split the string by whitespace and count the non-empty tokens. The split() method automatically handles multiple consecutive spaces.
Steps:
Time Complexity: O(n) – scan entire string once.
Space Complexity: O(n) – store words in list.
def count_words(sentence: str) -> int:
if not
Given a string, remove all spaces from it and return the result.
Example 1:
Input: "Hello World"
Output: "HelloWorld"Example 2:
Input: " Python Programming "
Output: "PythonProgramming"Example 3:
Input: "NoSpaces"
Output: "NoSpaces"Constraints:
Iterate through the string and build a new string containing only non-space characters. Alternatively, use built-in string methods for a more concise solution.
Steps:
Time Complexity: O(n) – examine each character once.
Space Complexity: O(n) – store result string.
def remove_spaces(s: str) -> str:
result =
Given a string, determine if it contains only digit characters (0-9). Return true if all characters are digits, false otherwise. Implement without using built-in isdigit() or similar functions.
Example 1:
Input: "12345"
Output: trueExample 2:
Input: "123a45"
Output: falseExample 3:
Input: ""
Output: falseConstraints:
Check each character's ASCII value to determine if it falls within the digit range (48-57 for '0'-'9'). Return false immediately if any character is not a digit.
Steps:
Time Complexity: O(n) – check each character once.
Space Complexity: O(1) – no additional storage needed.
def is_only_digits(s: str) -> bool
Given a string, find the character that appears most frequently. If there are multiple characters with the same maximum frequency, return the one that appears first.
Example 1:
Input: "banana"
Output: 'a' (appears 3 times)Example 2:
Input: "programming"
Output: 'g' (appears 2 times, first among ties)Example 3:
Input: "hello"
Output: 'l' (appears 2 times)Constraints:
Count the frequency of each character using a dictionary, then find the character with the maximum count. To handle ties, track the first character that achieves the maximum frequency.
Steps:
Time Complexity: O(n) – two passes through the string.
Space Complexity: O(k) – where k is the number of unique characters.
from collections import Counter
def max_occurring_char(
Given a string, remove all duplicate characters and keep only the first occurrence of each character. The order of characters should be maintained.
Example 1:
Input: "programming"
Output: "progamin"Example 2:
Input: "banana"
Output: "ban"Example 3:
Input: "hello"
Output: "helo"Constraints:
Use a set to track characters we've already seen. Iterate through the string and add characters to the result only if they haven't been seen before.
Steps:
Time Complexity: O(n) – single pass through the string.
Space Complexity: O(k) – where k is the number of unique characters.
def remove_duplicates(s: str) -> str
Given two strings, determine if they are equal without using the equality operator (==) or any built-in string comparison methods. Compare character-by-character.
Example 1:
Input: "hello", "hello"
Output: trueExample 2:
Input: "hello", "world"
Output: falseExample 3:
Input: "test", "testing"
Output: falseConstraints:
First check if lengths are equal. If not, strings cannot be equal. Then compare each character at the same index position using character comparison or ASCII values.
Steps:
Time Complexity: O(n) – compare each character once.
Space Complexity: O(1) – no additional storage needed.
def are_strings_equal(s1: str, s2
Given a string, count the frequency of each character and return the result as a dictionary/map. This is a fundamental hash-map problem.
Example 1:
Input: "banana"
Output: {'b': 1, 'a': 3, 'n': 2}Example 2:
Input: "hello"
Output: {'h': 1, 'e': 1, 'l': 2, 'o': 1}Example 3:
Input: "aabbcc"
Output: {'a': 2, 'b': 2, 'c': 2}Constraints:
Use a dictionary to store character frequencies. Iterate through the string and increment the count for each character encountered.
Steps:
Time Complexity: O(n) – single pass through the string.
Space Complexity: O(k) – where k is the number of unique characters.
def count_character_frequency(s: str) -> dict
Given a string, convert all lowercase letters to uppercase and all uppercase letters to lowercase without using built-in functions like upper() or lower(). Use ASCII value differences.
Example 1:
Input: "Hello World"
Output (to upper): "HELLO WORLD"
Output (to lower): "hello world"Example 2:
Input: "Python123"
Output (to upper): "PYTHON123"
Output (to lower): "python123"Example 3:
Input: "ABC xyz"
Output (to upper): "ABC XYZ"
Output (to lower): "abc xyz"Constraints:
Use ASCII value differences to convert case. The difference between uppercase and lowercase letters is 32 in ASCII. Lowercase 'a' is 97, uppercase 'A' is 65.
Steps:
Time Complexity: O(n) – process each character once.
Space Complexity: O(n) – store result string.
def to_uppercase(
Given a string, find its length without using built-in functions like len() or length(). Iterate manually to count characters.
Example 1:
Input: "Hello"
Output: 5Example 2:
Input: "Python Programming"
Output: 18Example 3:
Input: ""
Output: 0Constraints:
Initialize a counter to zero and iterate through the string, incrementing the counter for each character encountered.
Steps:
Time Complexity: O(n) – iterate through entire string once.
Space Complexity: O(1) – only use a counter variable.
def string_length(s: str) -> int:
count =
Given a string, find the length of the longest substring without repeating characters. Use sliding window technique for optimal solution.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: "abc" is the longest substringExample 2:
Input: "bbbbb"
Output: 1
Explanation: "b" is the longest substringExample 3:
Input: "pwwkew"
Output: 3
Explanation: "wke" is the longest substringConstraints:
Use the sliding window technique with a hash map to track character positions. Expand the window by moving the right pointer and shrink it when duplicates are found by moving the left pointer.
Steps:
Time Complexity: O(n) – single pass through string.
Space Complexity: O(min(n, m)) – where m is charset size.
def length_of_longest_substring
Two strings are isomorphic if characters in one string can be replaced to get the other string. Each character must map to exactly one character (one-to-one mapping).
Example 1:
Input: s = "egg", t = "add"
Output: true
Explanation: e→a, g→dExample 2:
Input: s = "foo", t = "bar"
Output: false
Explanation: o cannot map to both a and rExample 3:
Input: s = "paper", t = "title"
Output: true
Explanation: p→t, a→i, e→l, r→eConstraints:
Use two hash maps to maintain bidirectional mapping. One map tracks s→t mappings and another tracks t→s mappings to ensure one-to-one correspondence.
Steps:
Time Complexity: O(n) – single pass through strings.
Space Complexity: O(k) – where k is number of unique characters.
def is_isomorphic(s:
Given a string, count or list all palindromic substrings. A palindrome reads the same forwards and backwards.
Example 1:
Input: "aaa"
Output: 6
Explanation: "a", "a", "a", "aa", "aa", "aaa"Example 2:
Input: "abc"
Output: 3
Explanation: "a", "b", "c"Example 3:
Input: "racecar"
Output: 10
Explanation: Individual chars + "aceca", "cec", "aceca", "racecar"Constraints:
Expand around center approach: treat each character and each pair of characters as potential centers of palindromes. Expand outward while characters match.
Steps:
Time Complexity: O(n²) – expand from each center.
Space Complexity: O(1) for counting, O(n²) for storing all palindromes.
def count_palindromic_substrings(s:
Given an array of strings, find the longest common prefix string amongst all strings. If there is no common prefix, return an empty string.
Example 1:
Input: ["flower", "flow", "flight"]
Output: "fl"Example 2:
Input: ["dog", "racecar", "car"]
Output: ""
Explanation: No common prefixExample 3:
Input: ["interspecies", "interstellar", "interstate"]
Output: "inters"Constraints:
Use horizontal scanning: start with the first string as the prefix and iteratively reduce it by comparing with each subsequent string until you find the common prefix.
Steps:
Time Complexity: O(S) – where S is sum of all characters in all strings.
Space Complexity: O(1) – only store the prefix.
def longest_common_prefix(strs: list)
Implement basic Run-Length Encoding (RLE). Compress a string by replacing consecutive characters with the character followed by its count. If the compressed string is not shorter, return the original string.
Example 1:
Input: "aaabbc"
Output: "a3b2c1"Example 2:
Input: "abc"
Output: "abc"
Explanation: Compression doesn't help, return originalExample 3:
Input: "aabcccccaaa"
Output: "a2b1c5a3"Constraints:
Use two pointers or iterate through the string, counting consecutive characters. Build the compressed string character by character with counts.
Steps:
Time Complexity: O(n) – single pass through string.
Space Complexity: O(n) – for the result string.
def compress_string(s: str
Given a string and an integer k, remove k consecutive duplicate characters repeatedly until you can't remove any more.
Example 1:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: Remove "eee", then "ccc", then "bbb", then "ddd"Example 2:
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: No consecutive duplicates to removeExample 3:
Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"Constraints:
Use a stack to track characters and their counts. When we encounter k consecutive duplicates, remove them. Continue until no more removals are possible.
Steps:
Time Complexity: O(n) – single pass through string.
Space Complexity: O(n) – for the stack.
def remove_duplicates(s:
Given a string, check if it can be made empty by repeatedly removing pairs of characters like "ab" or "cd". Return true if the string can be completely removed, false otherwise.
Example 1:
Input: s = "aabbccdd"
Output: true
Explanation: Remove "aa", "bb", "cc", "dd"Example 2:
Input: s = "abacaba"
Output: false
Explanation: Cannot remove all charactersExample 3:
Input: s = "abcd"
Output: false
Explanation: "ab" and "cd" are valid pairs, but order mattersConstraints:
Use a stack to simulate the removal process. When we encounter a character that pairs with the top of the stack, remove both. If the stack is empty at the end, the string is valid.
Steps:
Time Complexity: O(n) – single pass through string.
Space Complexity: O(n) – for the stack.
Given two strings, find the minimum number of character changes needed to make them anagrams of each other. An anagram is a word formed by rearranging the letters of another word.
Example 1:
Input: s1 = "aab", s2 = "aba"
Output: 0
Explanation: Already anagramsExample 2:
Input: s1 = "leetcode", s2 = "practice"
Output: 5
Explanation: Need to change 5 charactersExample 3:
Input: s1 = "anagram", s2 = "mangaar"
Output: 0Constraints:
Count character frequencies in both strings. The difference in frequencies tells us how many characters need to be changed. For each character, calculate the absolute difference in counts and sum them up, then divide by 2 (since each change affects both strings).
Steps:
Time Complexity: O(n) – where n is string length.
Space Complexity: O(1) – only 26 characters to track.
def min_changes_for_anagram(s1: str
Given a string, sort it in decreasing order based on the frequency of characters. If two characters have the same frequency, maintain their original order or sort alphabetically.
Example 1:
Input: "tree"
Output: "eert" or "eetr"
Explanation: 'e' appears twice, 't' and 'r' appear onceExample 2:
Input: "cccaaa"
Output: "cccaaa" or "aaaccc"Example 3:
Input: "Aabb"
Output: "bbAa" or "bbaA"Constraints:
Count character frequencies, sort by frequency (descending), then build the result string by repeating each character according to its frequency.
Steps:
Time Complexity: O(n log n) – due to sorting.
Space Complexity: O(n) – for frequency map and result.
def frequency_sort(s: str) ->
Given an array of strings, group all the anagrams together. An anagram is a word formed by rearranging the letters of another word.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]Example 2:
Input: strs = [""]
Output: [[""]]Example 3:
Input: strs = ["a"]
Output: [["a"]]Constraints:
Use a hash map where the key is the sorted version of each string (or character frequency signature), and the value is a list of anagrams. All anagrams will have the same sorted key.
Steps:
Time Complexity: O(n × k log k) – where n is number of strings, k is average length.
Space Complexity: O(n × k) – for storing all strings.
def group_anagrams(strs: list) ->
Concatenating s1 with itself simulates all possible rotations because every cut point in s1 is now represented as a contiguous substring in doubled. The substring check answers the question in one go. Length equality is crucial; otherwise, s2 can never be a rotation.
Both implementations perform two passes: one to collect counts and another to locate the first unique character. The Counter version is concise and readable, while the ASCII array trades readability for constant-time access without hashing. Either version returns -1 when every character's count exceeds one.
The implementation carefully handles edge cases: leading whitespace is stripped, optional signs are detected at the beginning, and digit accumulation stops at the first non-digit character. The result is clamped to prevent 32-bit integer overflow.
The Counter approach directly compares character frequencies, which is efficient and readable. The sorting approach works by sorting both strings and comparing them - if they're anagrams, the sorted versions will be identical. The HashMap approach manually builds frequency maps and compares them, which is useful when you need more control over the counting process.
The manual version shows the underlying logic: iterate from the end of the string to the beginning, building the reversed string character by character. The Pythonic version uses slicing notation [::-1] which is concise and efficient. The Java version uses StringBuilder for efficient string concatenation, as direct string concatenation in Java can be inefficient due to string immutability.
The solution uses a set lookup for vowel detection, which provides O(1) average-case checking. We first verify that each character is alphabetic using isalpha() to ignore numbers, spaces, and special characters. The set contains both uppercase and lowercase vowels to handle case-insensitive checking efficiently.
The split() approach is the most Pythonic and efficient solution. It automatically handles multiple consecutive spaces and leading/trailing whitespace. The manual approach uses a state variable to track whether we're currently inside a word, incrementing the count when we transition from space to non-space. This demonstrates the underlying logic but is less efficient than the built-in split method.
The manual approach builds a result character by character, skipping spaces. Using a list and joining at the end is more efficient in Python than string concatenation. The replace() method is the simplest and most readable solution. The split-join approach works by splitting on whitespace and joining with an empty string, effectively removing all spaces.
The solution manually checks if each character is a digit by comparing its ASCII value or using direct character comparison. Both approaches work because characters can be compared directly in most languages. The ASCII value of '0' is 48 and '9' is 57, so any character outside this range is not a digit. This implementation avoids built-in functions like isdigit() as requested.
The Counter approach efficiently counts character frequencies and uses two passes: one to count and one to find the first character with maximum frequency. The manual approach demonstrates the underlying logic of frequency tracking. By iterating through the original string order when finding the maximum, we ensure that among tied characters, we return the one that appears first in the string.
The set-based approach efficiently tracks which characters have been seen using O(1) average-case lookups. LinkedHashSet in Java or dict keys in Python 3.7+ maintain insertion order, making them perfect for this problem. The algorithm preserves the order of first occurrence by processing characters sequentially and only adding new ones to the result.
The solution avoids using the == operator by comparing ASCII values of characters using ord(). We first manually compute the lengths by iterating through each string. If lengths differ, the strings cannot be equal. Then we compare characters at each position using their ASCII values. The iterator approach demonstrates an alternative method that doesn't require length calculation upfront.
This is a classic hash-map problem where we use a dictionary to count occurrences. The manual approach explicitly checks if a key exists before incrementing. The get() method provides a cleaner solution by returning a default value (0) if the key doesn't exist. Python's Counter class from collections module provides the most concise solution, automatically handling all the counting logic. All approaches have O(n) time complexity with O(k) space for unique characters.
The solution leverages the ASCII table structure where lowercase letters (a-z) range from 97-122 and uppercase letters (A-Z) range from 65-90. The consistent difference of 32 between corresponding uppercase and lowercase letters allows simple arithmetic conversion. We check the ASCII range of each character and apply the appropriate offset. Non-alphabetic characters remain unchanged since they don't fall within these ranges.
The simplest approach uses a for loop to iterate through each character, incrementing a counter. This works because Python's for loop automatically handles string iteration. The while loop approach uses exception handling to detect when we've reached the end of the string by attempting to access indices until an IndexError occurs. The enumerate approach demonstrates that even though we're using enumerate, we're still manually counting. All methods avoid the built-in len() function while achieving O(n) time complexity.
The sliding window approach maintains a window of unique characters. When we encounter a duplicate, we move the left pointer past the previous occurrence. The hash map approach is more efficient as it can jump the left pointer directly, while the set approach needs to incrementally remove characters. Both maintain the invariant that all characters in the current window are unique.
Isomorphic strings require bijective (one-to-one and onto) mapping between characters. Using two hash maps ensures that each character in s maps to exactly one character in t and vice versa. The transformation approach converts both strings to their pattern representation (first occurrence gets 0, second unique char gets 1, etc.) and compares these patterns. If patterns match, strings are isomorphic.
The expand-around-center technique efficiently finds palindromes by recognizing that every palindrome has a center. For odd-length palindromes, the center is a single character. For even-length palindromes, the center is between two characters. By expanding outward from each possible center and checking character equality, we can find all palindromic substrings in O(n²) time. Using a set allows us to count unique palindromes only.
The horizontal scanning approach starts with the first string as the prefix and iteratively shortens it by comparing with each subsequent string. The vertical scanning approach compares characters at the same position across all strings. The sorting approach leverages the fact that after sorting, the most different strings are at the extremes, so comparing only the first and last strings gives the common prefix. All approaches are efficient, with horizontal scanning being the most intuitive.
Run-Length Encoding (RLE) is a simple compression algorithm that replaces consecutive identical characters with the character followed by its count. The key is to track consecutive characters and append both the character and its count to the result. The two-pass optimization first calculates the compressed length to avoid building the string if it won't be shorter. Using a list and joining is more efficient than string concatenation in Python, while StringBuilder is optimal in Java.
The stack approach efficiently tracks consecutive characters and their counts. When we encounter the same character as the top of the stack, we increment its count. Once the count reaches k, we remove that entry from the stack. This approach processes the string in a single pass and handles all removals correctly. The recursive approach is more intuitive but less efficient as it may require multiple passes through the string.
def is_valid_after_removals(s: str, pairs: list = None) -> bool:
"""Check if string can be emptied by removing valid pairs"""
if pairs is None:
# Default pairs: adjacent characters that differ by 1 in ASCII
# This is a common pattern, but can be customized
pairs = [('a', 'b'), ('c', 'd'), ('e', 'f')]
# Create a mapping for quick lookup
pair_map = {}
for a, b in pairs:
pair_map[a] = b
pair_map[b] = a
stack = []
for char in s:
if stack and stack[-1] in pair_map:
# Check if current char pairs with top of stack
if pair_map[stack[-1]] == char:
stack.pop() # Remove the pair
else:
stack.append(char)
else:
stack.append(char)
return len(stack) == 0
# Alternative: Remove any two consecutive same characters
def is_valid_simple(s: str) -> bool:
"""Remove pairs of same consecutive characters"""
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return len(stack) == 0
print(is_valid_simple("aabbccdd")) # True
print(is_valid_simple("abacaba")) # False
print(is_valid_simple("aabb")) # True
print(is_valid_simple("abba")) # True (remove "bb", then "aa")The stack-based approach efficiently checks if a string can be completely removed by pairing operations. When we encounter a character that forms a valid pair with the top of the stack, we remove both. The key is defining what constitutes a "valid pair" - it could be same consecutive characters, adjacent characters in a sequence, or any custom rule. If the stack is empty at the end, all characters were successfully paired and removed, making the string valid.
To make two strings anagrams, we need to ensure they have the same character frequencies. The minimum number of changes is calculated by finding the difference in frequencies for each character. Since each character change affects both strings (we're changing one character in one string to match the other), we divide the total difference by 2. The array-based approach is efficient as it only uses O(26) space for lowercase English letters.
The solution involves counting character frequencies, then sorting characters by their frequency in descending order. For characters with the same frequency, we typically sort them alphabetically. The bucket sort approach can be more efficient for strings with limited character diversity, as it groups characters by frequency first, then sorts within each frequency group. The standard approach uses a frequency map and sorting, which is straightforward and works well for most cases.
Anagrams have the same character frequencies, so they can be grouped by a common key. The most common approach is to sort each string's characters and use the sorted string as a key. All anagrams will produce the same sorted key. Alternatively, we can use a character frequency array (count of each letter) as the key, which is more efficient for longer strings as it avoids sorting. The count array approach creates a tuple/string representation of the frequency counts, which serves as a unique identifier for each anagram group.