Forem: pythonic_solutions

28. Find the Index of the First Occurrence in a String. When To Use find( )

pythonic_solutions — Tue, 13 May 2025 13:55:17 +0000

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

The most efficient and Pythonic way to solve this problem would be using Python's built-in string method find(). This method returns the lowest index of the substring needle in the string haystack if found, and -1 if it's not found. It is optimized and much faster than manually iterating through the string.

Solution using find():

def strStr(haystack: str, needle: str) -> int:
return haystack.find(needle)

Explanation:
haystack.find(needle): This returns the index of the first occurrence of needle in haystack. If needle is not found, it returns -1.

This solution has a time complexity of O(n), where n is the length of haystack, because find() searches through the string efficiently.

Example 1:

haystack = "sadbutsad"
needle = "sad"
print(strStr(haystack, needle)) # Output: 0
Explanation:

The substring "sad" is found at index 0 in the string "sadbutsad", so the result is 0.

Example 2:

haystack = "leetcode"
needle = "leeto"
print(strStr(haystack, needle)) Output: -1
Explanation:

The substring "leeto" is not found in "leetcode", so the result is -1.

Why find() is efficient:

find() is implemented in C behind the scenes, making it much faster and more memory-efficient compared to manually looping through the string.
It automatically handles the substring search in the most optimized way, which is why it's the preferred method for this task.

when to use find( )

The find() method is very efficient for searching substrings within a string, but it's important to know when to use it. Below are the scenarios when you should consider using find():

Searching for a Substring's First Occurrence: Use find() when you want to locate the first occurrence of a substring within a larger string. It will return the index of the first occurrence or -1 if the substring isn't found.

Example:

haystack = "sadbutsad"
needle = "sad"
print(haystack.find(needle)) Output: 0
In this case, find() efficiently returns the index of the first occurrence of "sad".

When You Don’t Need to Handle Multiple Occurrences:
If you're only interested in the first occurrence of the substring and don’t need to know about subsequent occurrences, find() is a great choice. It returns the first index without needing any loops or extra code.
For Simple String Matching:
If you're doing basic string matching where the input strings are relatively small or average in size (i.e., they don’t require complex regular expressions or sophisticated string matching algorithms), find() is perfect.

Example:

haystack = "hello world"
needle = "world"
index = haystack.find(needle)
print(index) Output: 6
Here, we want to find the first occurrence of "world" in the string "hello world", which is at index 6.

When You Don’t Need to Worry About Case Sensitivity: find() is case-sensitive. If you need to do a case-insensitive search, you'd need to convert both strings to lower or upper case before calling find().

Example:

haystack = "Hello World"
needle = "hello"
print(haystack.lower().find(needle.lower())) Output: 0

For Strings with Small Lengths (Performance Consideration): The find() method is generally the fastest approach for substring searching in Python. If you're dealing with relatively small strings or strings that are commonly used in typical programming problems, find() will likely be the most efficient.

When not to use find():
When you need to handle multiple occurrences: If you need to find all occurrences of the substring, find() will

The find() method in Python is used for searching a substring within a string, and it returns the index of the first occurrence of the substring. If the substring is not found, it returns -1. Here's a breakdown of the cases where find() is useful:

Finding the First Occurrence of a Substring If you need to find the first occurrence of a substring within a string, find() is ideal. It returns the index of the first match.

If the substring does not exist, find() returns -1.

Example:

haystack = "hello world"
needle = "world"
index = haystack.find(needle)
print(index) Output: 6

Checking if a Substring Exists You can use find() to check if a substring exists in the main string. If it returns -1, the substring isn't present; otherwise, it returns the index where it is found.

Example:

haystack = "apple pie"
needle = "pie"
if haystack.find(needle) != -1:
print("Found!")
else:
print("Not found!")

Searching Within a Specific Range (Start and End) find() allows you to specify optional start and end arguments to limit the search to a specific part of the string. This is useful when you only want to search within a certain slice of the string.

Example:

haystack = "hello world"
needle = "o"
index = haystack.find(needle, 5) Start searching from index 5
print(index) Output: 7 (The first 'o' after index 5 is at position 7)

Case-Sensitive Search find() is case-sensitive by default. If the case of the substring matters in the search, find() will return the index only if the substring matches exactly in terms of both characters and case.

Example:

haystack = "Hello World"
needle = "hello"
print(haystack.find(needle)) Output: -1, since case matters

When You Don’t Need Regular Expressions
If you just need basic string matching without any advanced pattern matching, find() is the most efficient approach. For more complex matching patterns (like using wildcards or different string structures), you might want to use regular expressions (re module), but find() is sufficient for straightforward substring searches.
For Performance in Small to Medium String Searches
find() is highly optimized for searching within strings and is faster than manually iterating over the string or using more complex methods, especially when dealing with small to medium-sized strings. The performance benefits come from its native implementation in C.
Avoiding Manual Loops
Using find() avoids the need to manually loop through the string and check each substring. It abstracts the loop logic and provides a simpler, cleaner solution.

Example:

haystack = "find the needle in the haystack"
needle = "needle"
print(haystack.find(needle)) Output: 9, the first occurrence of "needle"

When You Only Need the First Occurrence If you're only interested in the first occurrence of the substring, using find() is preferable over using index() (which raises an exception when not found), or writing a loop to find the first occurrence manually.

When Not to Use find():

Multiple Occurrences: If you need to find all occurrences of a substring in the string, find() is not suitable. You would need a loop or use re.finditer() for multiple occurrences.

Pattern Matching: For more complex patterns, such as regular expressions (e.g., searching for numbers, special characters), you would want to use the re module instead of find().

Summary:

When to use find():

To locate the first occurrence of a substring in a string.
To check if a substring exists in the string.
When you don’t need regular expressions for pattern matching.
When you want a simple and efficient solution for small to medium strings.
To perform case-sensitive searches.

When not to use find():

When you need to handle multiple occurrences (use findall() or loops).
When you need advanced pattern matching (use regular expressions).

3. Longest Substring Without Repeating Characters Solved

pythonic_solutions — Tue, 13 May 2025 10:44:33 +0000

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.
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.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

Core Idea (Sliding Window with Two Pointers)

We want to find a window in the string that doesn't contain any repeating characters.
We use two pointers, left and right, to define this window.
A set (char_set) keeps track of the unique characters in the current window.
If we find a duplicate, we shrink the window from the left until the duplicate is removed.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

Why It’s Efficient:

Each character is added and removed at most once → O(n)
Set gives constant time lookup → fast

When to Use This Technique:

Use this sliding window + set pattern whenever:
You need the longest substring/subarray with no repeats
You need to maintain a dynamic window of valid elements

Time & Space Complexity:
Type Value
Time O(n) (each character is visited at most twice)
Space O(min(n, m)) where m is the character set size (e.g. 26 lowercase)

When to use enumerate( ) and dict ? More Pythonic

pythonic_solutions — Tue, 13 May 2025 09:12:38 +0000

✅ Full Working Examples

✅ Need both index and value (enumerate())

s = "cat"
for i, ch in enumerate(s):
print(f"Index: {i}, Character: {ch}")
Output:

Index: 0, Character: c
Index: 1, Character: a
Index: 2, Character: t

✅ Track last occurrence of characters (dict)

s = "abracadabra"
last_seen = {}
for i, ch in enumerate(s):
last_seen[ch] = i
print(last_seen) # {'a': 10, 'b': 8, 'r': 9, 'c': 4, 'd': 6}

✅ Fast key-based lookup (dict)

grades = {"Alice": 95, "Bob": 87, "Charlie": 92}
print(grades["Bob"]) # 87

✅ Replacing range(len(...)) with enumerate()

numbers = [10, 20, 30]

Less Pythonic
for i in range(len(numbers)):
print(i, numbers[i])

More Pythonic
for i, num in enumerate(numbers):
print(i, num)

✅ Mapping relationships (dict)

capital = {
"France": "Paris",
"Japan": "Tokyo",
"India": "New Delhi"
}
print(capital["Japan"]) # Tokyo

Check if All Characters Have Equal Number of Occurrences

pythonic_solutions — Mon, 12 May 2025 14:47:26 +0000

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

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc"
Output: true
Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.
Example 2:

Input: s = "aaabb"
Output: false
Explanation: The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        from collections import Counter

        freq = Counter(s)
        values = set(freq.values())
        return len(values) == 1

✅ Example 1: s = "abacbc"

freq = Counter(s) # {'a': 2, 'b': 2, 'c': 2}
freq.values() # dict_values([2, 2, 2])
set(freq.values()) # {2}
len(set(freq.values())) # 1 → True ✅
✔️ All characters occur 2 times → set has just one unique value (2)

❌ Example 2: s = "aaabb"

freq = Counter(s) # {'a': 3, 'b': 2}
freq.values() # dict_values([3, 2])
set(freq.values()) # {2, 3}
len(set(freq.values())) # 2 → False ❌
✖️ Frequencies differ (3 and 2) → set has two values → return False

✅ Example 3: s = "xyz"

freq = Counter(s) # {'x': 1, 'y': 1, 'z': 1}
freq.values() # dict_values([1, 1, 1])
set(freq.values()) # {1}
len(set(freq.values())) # 1 → True ✅
✔️ Each character occurs once → return True

❌ Example 4: s = "aaabbbcc"

freq = Counter(s) # {'a': 3, 'b': 3, 'c': 2}
freq.values() # dict_values([3, 3, 2])
set(freq.values()) # {2, 3}
len(set(freq.values())) # 2 → False ❌
✖️ Different counts → return False

✅ Example 5: s = "a"

freq = Counter(s) # {'a': 1}
freq.values() # dict_values([1])
set(freq.values()) # {1}
len(set(freq.values())) # 1 → True ✅
✔️ Only one character → always valid → return True

✅ Time Complexity:
Counter(s):

This goes through the entire string s once to count frequencies.

Time: O(n) where n is the length of the string.

freq.values():

Extracts the frequency values, which is proportional to the number of unique characters.

Worst case (e.g., all characters different): O(n)

set(freq.values()):

Building a set from up to n frequency values.

Time: O(k) where k is the number of unique characters (bounded by 26 if only lowercase letters).

len(values) == 1:

Constant time: O(1)

🔹 Total Time Complexity: O(n)

✅ Space Complexity:
freq (Counter):

Stores counts of each unique character.

Space: O(k) where k is the number of unique characters.

values (Set):

Stores unique frequencies.

Space: O(k) again.

🔹 Total Space Complexity: O(k)
Where k ≤ 26 if the input string contains only lowercase English letters.

Final Answer:
Time Complexity: O(n)

Space Complexity: O(k) (usually O(1) if alphabet is fixed)

Longest Common Prefix When Do You Need a Zip? Let's see by solving this : Pythonic Solution

pythonic_solutions — Mon, 12 May 2025 13:57:03 +0000

Understanding zip(*strs) for Longest Common Prefix in Python

Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Examples

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

Input: strs = ["dog", "racecar", "car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Constraints
1 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] consists of only lowercase English letters if non-empty

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        for chars in zip(*strs):
            if len(set(chars)) == 1:
                prefix += chars[0]
            else:
                break
        return prefix

How It Works

zip(*strs)
Transposes the list of strings by grouping characters from the same index in each string.

Example:

strs = ["flower", "flow", "flight"]
list(zip(*strs))
Output: [('f','f','f'), ('l','l','l'), ('o','o','i'), ...]

set(chars)
Used to check if all characters in the same position across the strings are the same.

If all match, the character is added to the prefix.

If not, the loop breaks.

Step-by-step Example
Given:

strs = ["cat", "car", "cap"] Position Word 1 Word 2 Word 3 0 c c c 1 a a a 2 t r p

Transposed with zip(*strs):

[('c', 'c', 'c'), ('a', 'a', 'a'), ('t', 'r', 'p')]
We loop through these tuples and compare:

('c', 'c', 'c') → all same → add 'c'

('a', 'a', 'a') → all same → add 'a'

('t', 'r', 'p') → not all same → stop

Final prefix: "ca"

What is zip() in Python?

The zip() function combines elements from multiple iterables (lists, tuples, etc.) by index.

Basic Example

names = ["Alice", "Bob", "Charlie"]
ages = [25, 30, 35]

for pair in zip(names, ages):
print(pair)

Output:
('Alice', 25)
('Bob', 30)
('Charlie', 35)
What does zip(*strs) do?
It transposes the input, grouping characters by their positions.

strs = ["dog", "doll", "door"]
list(zip(*strs))
Output: [('d', 'd', 'd'), ('o', 'o', 'o'), ('g', 'l', 'o')]
This allows column-wise comparison of characters.

Why Use zip(*strs)?

Clean and concise
Automatically stops at the shortest string
Easier than looping with indices
Ideal for comparing strings character by character

Use Cases for zip()

Processing multiple sequences in parallel

`students = ['Alice', 'Bob']
scores = [90, 95]

for name, score in zip(students, scores):
print(name, score)
`
Transpose a matrix

matrix = [
[1, 2, 3],
[4, 5, 6]
]

transposed = list(zip(*matrix))
Output: [(1, 4), (2, 5), (3, 6)]

Compare strings by character positions

words = ["flow", "flower", "flight"]

for letters in zip(*words):
print(letters)
When Not to Use zip()
When working with a single list

When lists are of unequal length and you need the remaining elements

When element position doesn’t matter

Practice Scenarios
Scenario 1: Combine three lists into tuples

a = [1, 2]
b = ['x', 'y']
c = ['apple', 'banana']
list(zip(a, b, c))

Output: [(1, 'x', 'apple'), (2, 'y', 'banana')]
Scenario 2: Check if two lists differ element-wise

`a = [10, 20, 30]
b = [10, 25, 30]

for x, y in zip(a, b):
if x != y:
print(f"Mismatch: {x} ≠ {y}")`

Scenario 3: Longest Common Prefix (Interview Example)

products = ["macbook", "macpro", "macmini", "imac"]

prefix = ""
for chars in zip(*products):
if len(set(chars)) == 1:
prefix += chars[0]
else:
break

print(prefix) # Output: "mac"
Time and Space Complexity
Time Complexity: O(S) where S is the sum of all characters across all strings.

Space Complexity: O(1) (excluding the result), since we only use a few extra variables.

Summary
Use zip(*strs) to align strings character-wise.

It’s one of the most Pythonic ways to solve the longest common prefix problem.

Helps simplify logic, reduce index errors, and improve readability.

2299. Strong Password Checker II

pythonic_solutions — Sun, 12 Jun 2022 03:53:34 +0000

A password is said to be strong if it satisfies all the following criteria:

It has at least 8 characters.
It contains at least one lowercase letter.
It contains at least one uppercase letter.
It contains at least one digit.
It contains at least one special character. The special characters are the characters in the following string: "!@#$%^&*()-+".
It does not contain 2 of the same character in adjacent positions (i.e., "aab" violates this condition, but "aba" does not).
Given a string password, return true if it is a strong password. Otherwise, return false

class Solution {
public:
    bool strongPasswordCheckerII(string &p) {
        if(p.size()<8) return false;
        bool low =false, upper = false,digit = false,special =false;
        for(auto it:p){
            if(it>='a' and it<='z')low = true;
        else if(it>='A' and it<='Z')upper = true;
        else if(isdigit(it)) digit = true;
            else special = true;

        }
        //check the 6th condition 
        for(int i=0;i+i<p.size();i++) if(p[i] == p[i+1]) return false;
        if(low and upper and special and digit) return true;
        return false;

    }
};

Iterative Inorder Traversal - Leetcode

pythonic_solutions — Mon, 06 Jun 2022 09:11:09 +0000

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        //first, we create a stack 
        stack<TreeNode*>st;
        //create a node and assign it to root 
        TreeNode*node = root;
        //declare a vector which stores inorder 
        vector<int>inorder;
        while(true){
        //if the node that is the root is not null, we take that and insert it into stack
            if(node != NULL){
                st.push(node);
        //after pushing into stack, move to the left 
                node = node->left;
            }
            else{
            //if you traverse a tree and end up getting null, this is what you need to do 
            //if stack is empty there are no nodes to travel
                if(st.empty() == true) break;
            //else if the st is not empty, whatever is at the top we will take it 
                node = st.top();
                st.pop();
            //and this is eventually inorder
                inorder.push_back(node->val);
                node = node->right;
            }

        }
        return inorder;
    }
};

//TC :O(n) , as we traverse every node 
// SC :O(h) , height of the binary tree, in worst case it is skewed tree

Iterative Preorder Traversal

pythonic_solutions — Mon, 06 Jun 2022 08:26:41 +0000

We need to use a stack for a iterative traversal and traverse from right to left , as stack follows ( Last In First Out)

Below is the implementation of the code:-


class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        //we need to declare a vector 
     vector<int> preorder;
        //if the tree is empty , you return empty preorder 
        if(root == NULL) return preorder;


        //you then initialize the stack 
        stack<TreeNode*>st;
        st.push(root);

        //you keep iterating on the stack till it is non-empty 
        while(!st.empty()){
        //now you get the top most element 
            root = st.top();
            st.pop();
            preorder.push_back(root->val);
        //check if it has a right or left on it and put it into the stack 
            if(root->right!=NULL){
                st.push(root->right);
            }
             if(root->left!=NULL){
                st.push(root->left);
            }


        }

        return preorder;
    }
};

Time Complexity :O(n) , because we are travelling every node
Space Complexity :O(n) , ( this is the worst case in case of
skewed tree)

160. Intersection of Two Linked Lists - Leetcode

pythonic_solutions — Mon, 06 Jun 2022 07:35:48 +0000

Naive Approach :

Find the length of both the lists
Find the difference in the length of both the lists
Then start checking the equality for the nodes
Once we find equal node return that node
otherwise if we reach at the end return the null

There is a better way to do it:

We are going to traverse the shorter one and longer one at the same time
We are going to set pointers to the heads of both of these.
When we get at the end of the shorter one, we set the pointer to the head of the longer one.
When we get at the end of the longer one, we set the pointer to the head of the shorter one.

Here, is the code of the implementation

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        if(headA == NULL|| headB == NULL) return NULL;
        ListNode*a_pointer = headA;
        ListNode*b_pointer = headB;

        //while the nodes are not equal 
        while(a_pointer != b_pointer ){
            if(a_pointer == NULL){
              //this means it is at the end of the list 
                a_pointer = headB;   
            } 

        else{
            a_pointer = a_pointer->next;
        }

              if(b_pointer == NULL){
               //this means it is at the end of the list 
                b_pointer = headA;   
              } 

        else{
            b_pointer = b_pointer->next;
        }
        }
        return a_pointer;
    }
};

Sum Tree

pythonic_solutions — Sat, 04 Jun 2022 10:07:19 +0000

This post discusses the solution of the problem -

We need to solve this problem using Children Sum Property, which means sum of left and right child should be equal to its root. A tree with single node, is also considered to be following children sum property.A empty tree is also considered to be following Children Sum Property.

Below is the solution of the problem.

class Solution
{
    public:

    int findSum(Node*root){
        if(!root) return 0;
        return root->data +findSum(root->left)+findSum(root->right);
    }
    bool isSumTree(Node* root)
    {
         // Your code here
         if(!root) return true;
         if(!root->left && !root->right) return true;

         if(findSum(root->left)+findSum(root->right) == root->data)
         return (isSumTree(root->left) && isSumTree(root->right));
         else return false;
    }
};

Construct a Binary Tree from Inorder and Postorder

pythonic_solutions — Sat, 04 Jun 2022 09:50:04 +0000

When we are given a root,left and right subtree :

Inorder : Left Root Right
Preorder : Root Left Right

We can get the root from the Preorder traversal, and the first element from the Preorder traversal is Root.If we locate the root, we can find the left and right side of the tree easily. We can follow the similar fashion and construct the whole tree.

Here is the code of the solution

class Solution{
    public:
    int order=0;
    Node* build(int in[],int pre[],int s,int e){
        if(s>e){
            return NULL;
        }
        Node* root=new Node(pre[order++]);
        int index=0;
        for(int i=s;i<=e;i++){
            if(in[i]==root->data){
                index=i;
                break;
            }
        }
        root->left=build(in,pre,s,index-1);
        root->right=build(in,pre,index+1,e);
        return root;
    }
    Node* buildTree(int in[],int pre[], int n)
    {
        return build(in,pre,0,n-1);
        // Code here
    }
};

Maximum Subarray - Leetcode Solution

pythonic_solutions — Tue, 22 Feb 2022 16:43:11 +0000

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

We need to use Kadane's Algorithm here

//Kadane's Algorithm

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans =INT_MIN,sum =0;
        int n=nums.size();
        for(int i=0;i<n;++i){
           sum+=nums[i];
           ans = max(ans,sum);
        if(sum<0)
            sum=0;

        }
        return ans;

        }      

};