Valid Anagram Problem Solution

Regular Expression Matching 🔗 Problem Link LeetCode – Regular Expression Matching ⸻ 📌 Problem Statement Implement regular expression matching with support for: • . → Matches any single character • * → Matches zero or more of the preceding element The matching should cover the entire input string, not partial. ⸻ 🎯 Objective Given two strings: • s → Input string • p → Pattern Return true if s matches pattern p, otherwise return false. ⸻ 🧠 Approach Used 1️⃣ Dynamic Programming (DP) We use a 2D boolean table: • dp[i][j] represents → Whether first i characters of string s match → First j characters of pattern p. ⸻ 2️⃣ Base Case • dp[0][0] = true → Empty string matches empty pattern. • Handle patterns like a*, a*b*, etc. Because * can represent zero occurrences. ⸻ 3️⃣ Pattern Matching Logic Case 1: Direct Match or . If: • Current characters are equal OR • Pattern character is . Then: • Value depends on previous diagonal state → dp[i][j] = dp[i-1][j-1] ⸻ Case 2: * Character When pattern character is *, two possibilities exist: 1. Zero occurrences Ignore previous character and * → Move two steps back in pattern 2. One or more occurrences If previous pattern character matches current string character → Stay in same pattern position → Move string pointer This is the key idea of the problem. ⸻ ⏱ Time Complexity • O(m × n) Where: • m = length of string s • n = length of pattern p ⸻ 💾 Space Complexity • O(m × n) Due to 2D DP table. ⸻ 🧩 Key Concepts Covered • Dynamic Programming • 2D DP Table • Pattern Matching • Edge Case Handling • String Manipulation ⸻ 📈 Result • Accepted on LeetCode • All test cases passed • Efficient solution using DP #java #dsa #javaprogram #array #leetcode #solution #data #structure #algorithm #javadeveloper

🚀 DSA Series: Insertion Sort Explained Simply Insertion Sort is a simple and intuitive sorting algorithm. It works the same way we arrange playing cards in our hands. 🃏 Real-Life Example: When we pick cards one by one, we insert each new card into the correct position among the already sorted cards in our hand. Insertion Sort follows the same idea. 💻 Java Code class Solution {     public void insertionSort(int arr[]) {         int n = arr.length;         for(int i = 1; i < n; i++) {             int curr = arr[i];             int j = i - 1;             while(j >= 0 && arr[j] > curr) {                 arr[j + 1] = arr[j];                 j--;             }             arr[j + 1] = curr;         }     } } 🧠 How it Works Example: Array → 5 3 4 1 2 Step 1 → 3 5 4 1 2 Step 2 → 3 4 5 1 2 Step 3 → 1 3 4 5 2 Step 4 → 1 2 3 4 5 Each element is inserted into the correct position in the already sorted part of the array. 📊 Time Complexity Best Case: O(n) (Already Sorted) Average Case: O(n²) Worst Case: O(n²) 📌 Space Complexity: O(1) 💡 Key Idea: Instead of repeatedly swapping like Bubble Sort, Insertion Sort shifts elements and inserts the current element in the correct position. #DSA #Java #InsertionSort #SortingAlgorithms #CodingInterview #SoftwareEngineering

🚀 Day 18/30– DSA Challenge 📌 LeetCode Problem – Search Insert Position 📝 Problem Statement Given a sorted array nums and a target value, return the index if found. If not found, return the index where it would be inserted in order. 📌 Example Input: nums = [1,3,5,6] target = 2 Output: 1 Explanation: 2 should be inserted at index 1. 💡 Key Insight This is a binary search variation. 👉 If element exists → return index 👉 If not → return the position where it should be And that position is exactly where left ends after the loop. 🚀 Algorithm 1️⃣ Initialize: left = 0 right = n - 1 2️⃣ While left <= right: Find mid If equal → return mid If smaller → move left Else → move right 3️⃣ If not found → return left ✅ Java Code (Optimal O(log n)) class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } } ⏱ Complexity Time Complexity: O(log n) Space Complexity: O(1) 📊 Performance ⚡ Runtime: 0 ms (Beats 100%) 💾 Memory: ~44 MB 📚 Key Learnings – Day 18 ✔ Binary Search is more than just finding elements ✔ “Insert position” problems are common variations ✔ Final value of left is very important ✔ Always avoid overflow → use mid = left + (right - left)/2 Simple problem. Strong concept. Perfect execution. Day 18 completed. Consistency continues 💪🔥 #30DaysOfCode #DSA #Java #InterviewPreparation #ProblemSolving #CodingJourney #BinarySearch #LeetCode

🚀 Day 22 of #75DaysofLeetCode LeetCode Problem Solved: Determine if Two Strings Are Close (1657) Another interesting String + Frequency Analysis problem from LeetCode! 🔹 Problem: Two strings are considered close if we can transform one into the other using: 1️⃣ Swap any two characters (rearranging characters). 2️⃣ Transform all occurrences of one character into another existing character and vice versa. We need to determine whether word1 can be converted into word2 using these operations. 💡 Key Insights: To make two strings close, three conditions must hold: ✔️ Both strings must have the same length. ✔️ Both strings must contain the same set of characters. ✔️ The frequency distribution of characters must match after sorting. Why? Because operation 2 allows us to swap character frequencies between existing characters. 💻 Java Solution: import java.util.*; class Solution { public boolean closeStrings(String word1, String word2) { if(word1.length() != word2.length()) return false; int[] freq1 = new int[26]; int[] freq2 = new int[26]; for(char c : word1.toCharArray()) freq1[c - 'a']++; for(char c : word2.toCharArray()) freq2[c - 'a']++; for(int i = 0; i < 26; i++){ if((freq1[i] == 0 && freq2[i] != 0) || (freq1[i] != 0 && freq2[i] == 0)) return false; } Arrays.sort(freq1); Arrays.sort(freq2); return Arrays.equals(freq1, freq2); } } 📊 Complexity Analysis: ⏱ Time Complexity: O(n) 📦 Space Complexity: O(1) Problems like this help strengthen understanding of hashing, frequency counting, and string manipulation, which are common in coding interviews. #LeetCode #DSA #Java #CodingPractice #Algorithms #ProblemSolving #SoftwareEngineering

🚀 𝗗𝗮𝘆 12 𝗼𝗳 𝗖𝗼𝗻𝘀𝗶𝘀𝘁𝗲𝗻𝗰𝘆 — Solved “Valid Anagram” on LeetCode Today I worked on a classic string problem: Valid Anagram — a great question to strengthen understanding of frequency counting and optimized string handling. 🔍 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗨𝗻𝗱𝗲𝗿𝘀𝘁𝗮𝗻𝗱𝗶𝗻𝗴 Given two strings s and t, determine whether t is an anagram of s. 👉 Anagram means both strings contain the same characters with the same frequency. 🧠 𝗕𝗿𝘂𝘁𝗲 𝗙𝗼𝗿𝗰𝗲 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 Sort both strings Compare them ⏱ Time Complexity: O(n log n) 👉 Works fine but not optimal for interviews ⚡ 𝗢𝗽𝘁𝗶𝗺𝗶𝘇𝗲𝗱 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 (Used Today) Instead of sorting, I used frequency counting with arrays. ✅ 𝗦𝘁𝗲𝗽𝘀: If lengths are different → return false Create two arrays of size 26 (for lowercase letters) Count frequency of characters in both strings Compare both frequency arrays 💻 𝗖𝗼𝗱𝗲 𝗜𝗻𝘀𝗶𝗴𝗵𝘁 Increment count for characters in s Increment count for characters in t Compare both arrays → if all values match → anagram ✅ 📌 𝗘𝘅𝗮𝗺𝗽𝗹𝗲 s = "anagram" t = "nagaram" ✔ Same frequency → Valid Anagram ⏱ 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 𝗔𝗻𝗮𝗹𝘆𝘀𝗶𝘀 Time: O(n) Space: O(1) (constant size array) 💡 𝗞𝗲𝘆 𝗟𝗲𝗮𝗿𝗻𝗶𝗻𝗴 Always try to replace sorting with counting when dealing with characters Frequency array is a powerful optimization technique Writing clean and optimal code improves both performance and interview confidence Grateful for continuous learning and growth 🙏 Consistency is the real game changer 💯 #LeetCode #DSA #Java #ProblemSolving #CodingJourney #100DaysOfCode #TechLearning #SoftwareDevelopment

🚀 DSA Series: Merge Sort Explained Simply Merge Sort is a Divide and Conquer sorting algorithm. It works by dividing the array into smaller parts, sorting them, and then merging them back together. 🧠 Idea: 1️⃣ Divide the array into two halves 2️⃣ Sort both halves recursively 3️⃣ Merge the sorted halves 💻 Java Code class Solution { void merge(int arr[], int l, int mid, int r) { int n1 = mid - l + 1; int n2 = r - mid; int left[] = new int[n1]; int right[] = new int[n2]; for(int i = 0; i < n1; i++) left[i] = arr[l + i]; for(int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = l; while(i < n1 && j < n2) { if(left[i] <= right[j]) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } while(i < n1) { arr[k] = left[i]; i++; k++; } while(j < n2) { arr[k] = right[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if(l < r) { int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } } } 📊 Time Complexity Best Case: O(n log n) Average Case: O(n log n) Worst Case: O(n log n) 📌 Space Complexity: O(n) 💡 Key Point: Merge Sort is stable and guarantees O(n log n) performance, but it requires extra memory. #DSA #Java #MergeSort #SortingAlgorithms #CodingInterview #SoftwareEngineering

𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞 𝐃𝐚𝐢𝐥𝐲 𝐂𝐡𝐚𝐥𝐥𝐞𝐧𝐠𝐞: 1784.Check if Binary String Has At Most One Segment of Ones Today’s challenge was a short but insightful problem that demonstrates how recognizing patterns in a binary string can lead to an extremely elegant solution. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐮𝐦𝐦𝐚𝐫𝐲: We are given a binary string s consisting only of '0' and '1'. The task is to determine whether the string contains at most one continuous segment of '1'. In other words, once a '0' appears after a '1', there should not be another '1' later in the string. If there is more than one segment of '1', return false. Otherwise, return true. 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: The key observation is very simple. If a binary string has more than one segment of '1', the pattern "01" must appear somewhere in the string. Why? A valid string with only one segment of ones looks like: 0001111000 But an invalid string with multiple segments would look like: 11100111 Notice the transition "01" which indicates that ones started again after a zero. Therefore, the entire problem reduces to checking whether the substring "01" exists. If "01" is present → there are multiple segments of '1'. If "01" is absent → there is at most one segment. This allows us to solve the problem in a single line using the built-in string function. 𝐂𝐨𝐝𝐞 𝐒𝐧𝐢𝐩𝐩𝐞𝐭 (Java): class Solution { public boolean checkOnesSegment(String s) { return !s.contains("01"); } } 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 𝐀𝐧𝐚𝐥𝐲𝐬𝐢𝐬: Time Complexity: O(n) Space Complexity: O(1) We scan the string once to check if the pattern "01" exists. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬: Sometimes the best solution is identifying a simple pattern instead of simulating the entire process. Understanding how transitions occur in binary strings can simplify many problems. Leveraging built-in string functions can make solutions both clean and efficient. A great reminder that even small problems can reinforce strong pattern-recognition skills. #LeetCode #DSA #Java #ProblemSolving #Algorithms #BinaryStrings #CodingPractice #Consistency #100DaysOfCode #LearningJourney

Day 74/365 – Remove Duplicate Letters Problem: Given a string s, remove duplicate letters so that each letter appears once and the result is the smallest lexicographical order possible. Example: "bcabc" → "abc" "cbacdcbc" → "acdb" 💡 Key Idea Use a Monotonic Stack to maintain characters in lexicographically smallest order. We also track: • Last occurrence of each character • Whether a character is already used in the result 🧠 Approach 1️⃣ Record the last index of each character. 2️⃣ Traverse the string. 3️⃣ Skip characters already included. 4️⃣ While stack top is bigger than current character and it appears later again, remove it to get a smaller result. 5️⃣ Push current character into the stack. 📦 Key Logic while(!stack.isEmpty() && stack.peek() > c && lastIndex[stack.peek() - 'a'] > i) { visited[stack.pop() - 'a'] = false; } This ensures: Lexicographically smallest result Each character appears only once 📊 Complexity ⏱ Time: O(n) 📦 Space: O(1) (since only 26 letters) ✨ Key Learning This is a classic Monotonic Stack + Greedy problem. Pattern to remember: 👉 Remove previous larger elements if they appear again later. This pattern appears in problems like: Smallest Subsequence Remove K Digits Monotonic stack optimization problems #Day74 #365DaysOfCode #LeetCode #MonotonicStack #GreedyAlgorithm #DataStructures #Algorithms #Java #DSA #CodingInterview

𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞 𝐇𝐚𝐫𝐝 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝: 𝐅𝐢𝐧𝐝 𝐭𝐡𝐞 𝐒𝐭𝐫𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐋𝐂𝐏 𝐐𝐮𝐞𝐬𝐭𝐢𝐨𝐧 𝐋𝐢𝐧𝐤 :https://lnkd.in/gPQ5WExk 𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧 𝐋𝐢𝐧𝐤 : https://lnkd.in/gYpvYnaW Today I worked on an interesting 𝐡𝐚𝐫𝐝 𝐩𝐫𝐨𝐛𝐥𝐞𝐦: 𝐅𝐢𝐧𝐝 𝐭𝐡𝐞 𝐒𝐭𝐫𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐋𝐂𝐏. The problem provides an 𝐋𝐂𝐏 (𝐋𝐨𝐧𝐠𝐞𝐬𝐭 𝐂𝐨𝐦𝐦𝐨𝐧 𝐏𝐫𝐞𝐟𝐢𝐱) 𝐦𝐚𝐭𝐫𝐢𝐱 and asks us to construct the lexicographically smallest string that satisfies this matrix.  𝐊𝐞𝐲 𝐈𝐝𝐞𝐚 Instead of constructing substrings directly, the approach is: 1️⃣ Start assigning characters from 'a' onward. 2️⃣ If lcp[i][j] > 0, it means the substrings starting at i and j share the same first character. 3️⃣ Propagate the same character across positions where the LCP value indicates a match. 4️⃣ Finally, validate the entire LCP matrix using the rule: lcp[i][j] = (word[i] == word[j]) ? 1 + lcp[i+1][j+1] : 0 If any condition fails, no valid string exists.  𝐖𝐡𝐚𝐭 𝐈 𝐥𝐞𝐚𝐫𝐧𝐞𝐝 • How LCP matrices represent relationships between substrings • Constructing strings using greedy character assignment • Validating constraints using dynamic programming relations • Importance of verifying generated structures against given matrices Problems like this really sharpen string manipulation + matrix reasoning skills. Always fun pushing through Hard-level challenges! #LeetCode #DataStructures #Algorithms #CodingPractice #Java #ProblemSolving

🚀 PART of Coding Practice – Finding the Most Frequent Element in an Array (Java) Today I worked on a classic yet important problem in Data Structures & Algorithms 👇 🔍 Problem Statement Given an array of integers, find the most frequent element (the element that appears the highest number of times). 💡 My Approach (Brute Force) I used a nested loop approach: For each element, I counted how many times it appears in the array. Tracked the maximum count. Stored the element with the highest frequency. 👉 Time Complexity: O(n²) 👉 Space Complexity: O(1) 🧠 Code Logic in Simple Words Take input array Loop through each element Count its frequency using another loop Update max frequency and result Print the most frequent element 📌 Sample Input Array: [1, 2, 2, 2, 3] ✅ Output Most Frequent Element: 2 🧪 Test Cases I Tried ✔️ Test Case 1 Input: [4, 4, 5, 5, 5, 6] Output: 5 ✔️ Test Case 2 (All Unique) Input: [1, 2, 3, 4] Output: 1 (or any first element since all frequencies are same) ✔️ Test Case 3 (Single Element) Input: [7] Output: 7 ✔️ Test Case 4 (Negative Numbers) Input: [-1, -1, -2, -2, -2] Output: -2 🤔 Can We Do It Even Better? Can you solve this problem using: HashMap? Sorting? Without extra space? ❓ Challenge for You 💬 Try solving this: Find the top 2 most frequent elements in an array. 📈 My Learning Today Importance of optimization Difference between Brute Force vs Efficient Approach How frequency-based problems are common in interviews I’m consistently improving step by step 💪 Would love your suggestions on improving this further 🙌 #Java #DSA #CodingJourney #ProblemSolving #DataStructures #100DaysOfCode #Learning #Tech #InterviewPreparation #DeveloperJourney