Day 4 - Solving 5 String & Integer DSA Problems

📑 Table of Contents

1. Reverse Integer

2. First Unique Character in a String

3. Valid Anagram

4. Valid Palindrome

5. String to Integer

6. Conclusion

🔍 Introduction

On Day 4 of my 90 Days DSA Challenge, I focused on strengthening my problem-solving skills with a mix of string-based and integer problems. These problems are essential for improving logical thinking and preparing for coding interviews. I’ve included clear explanations, code snippets, and dry run insights.

✅ Problem 1 – [Reverse Integer]

🧾 Approach:

To solve the Reverse Integer problem, we apply the classic number reversal method by extracting digits using modulus (%) and constructing the reversed number. However, since we’re working with 32-bit signed integers, we must check for overflow before pushing digits into the result.

🔁 Step-by-step logic:

1. Extract the last digit using temp = val % 10.

2. Before multiplying the result ans by 10 and adding temp, check for overflow conditions.

3. If all checks pass, update the result: ans = ans * 10 + temp.

4. Divide val by 10 to move to the next digit.

🛑 Overflow Edge Cases:

We must return 0 if reversing causes the number to go out of the 32-bit integer range:

• Case 1: ans > Integer.MAX_VALUE / 10
  ⇒ Multiplying by 10 will definitely overflow.
  → if(ans > Integer.MAX_VALUE / 10) return 0;

• Case 2: ans == Integer.MAX_VALUE / 10 && temp > 7
  ⇒ Final digit will exceed max limit (2147483647).
  → if(ans == Integer.MAX_VALUE / 10 && temp > 7) return 0;

• Case 3: ans < Integer.MIN_VALUE / 10
  ⇒ Multiplying by 10 will underflow.
  → if(ans < Integer.MIN_VALUE / 10) return 0;

• Case 4: ans == Integer.MIN_VALUE / 10 && temp < -8
  ⇒ Final digit will exceed min limit (−2147483648).
  → if(ans == Integer.MIN_VALUE / 10 && temp < -8) return 0;

This careful handling ensures we don’t encounter any integer overflows during reversal.

class Solution {
    public int reverse(int x) {
        int val=x;
        int ans=0;
        while(val!=0){
            int temp=val%10;
            if(ans>Integer.MAX_VALUE/10){
                return 0;
            }
            if(ans==Integer.MAX_VALUE/10 && temp>7){
                return 0;
            }
            if(ans<Integer.MIN_VALUE/10){
                return 0;
            }
            if(ans==Integer.MIN_VALUE/10 && temp<-8){
                return 0;
            }
            ans=(ans*10)+temp;
             val=val/10;
        }
        return ans;
    }
}

💡 Key Observations or Dry Run:

Let’s dry run the input x = 123 to understand how the reversal logic works.

🔄 Initial Values:

• val = 123

• ans = 0

✅ Iteration 1:

• temp = 123 % 10 = 3

• No overflow check triggers.

• ans = 0 * 10 + 3 = 3

• val = 123 / 10 = 12

✅ Iteration 2:

• temp = 12 % 10 = 2

• No overflow check triggers.

• ans = 3 * 10 + 2 = 32

• val = 12 / 10 = 1

✅ Iteration 3:

• temp = 1 % 10 = 1

• No overflow check triggers.

• ans = 32 * 10 + 1 = 321

• val = 1 / 10 = 0

✅ Final Output:

• val = 0, loop ends.

• Return ans = 321

✔️ Works as expected — the number has been reversed correctly.

🧠 What I Learned:

I learned how to reverse an integer while handling edge cases related to 32-bit signed integer overflow, and how crucial it is to check boundary conditions before performing operations.

Also this problem is important before we solve the String to Integer Problem

✅ Problem 2 – [First Unique Character in a String]

🚀 Approach:

1. Goal:
   We are asked to find the index of the first non-repeating (unique) character in a given string. If no such character exists, return -1.

2. Step 1 – Frequency Counting:

   • We use a HashMap<Character, Integer> to count how many times each character appears in the string.

   • Loop through the string using a for-each loop and update the frequency using

   • map.put(c, map.getOrDefault(c, 0) + 1).

3. Step 2 – Identifying the Unique Character:

   • Now that we know the frequency of every character, we loop through the string again.

   • For each character, we check if(map.get(char) == 1).

   • If true, we return the current index, since this is the first unique character.

4. Step 3 – No Unique Character:

   • If the loop completes and no character with frequency 1 is found, return -1.

class Solution {
    public int firstUniqChar(String s) {
      Map<Character,Integer>map=new HashMap<>();
      for(char c : s.toCharArray())  {
        map.put(c,map.getOrDefault(c,0)+1);
      }
      for(int i=0;i<s.length();i++){
        if(map.get(s.charAt(i))==1){
            return i;
        }
      }
      return -1;
    }
}

📦 Physical Representation:

Let’s assume the input string is:

String s = "leetcode";

---

🔁 s.toCharArray():

This converts the string into a character array like this:

So, s.toCharArray() gives us:

['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']

And now you can loop through it using a for-each loop:

for(char c : s.toCharArray()) {
    // access each character like: c = 'l', then 'e', ...
}

---

🎯 s.charAt(i):

This accesses each character directly by index.

Example:

s.charAt(0) = 'l'
s.charAt(1) = 'e'
s.charAt(2) = 'e'
s.charAt(3) = 't'
...

Used in a loop:

for(int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);  // Picks each character by its index
}

💡 Key Observations or Dry Run

Let's take the example input:

String s = "leetcode";

1. Convert to Character Array:
   s.toCharArray() transforms "leetcode" into:

    ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']
   

2. Frequency Counting:
   As we loop through each character, we build a frequency map:

   • 'l' → count becomes 1

   • 'e' → count becomes 1; next occurrence makes it 2

   • 't' → count becomes 1

   • 'c' → count becomes 1

   • 'o' → count becomes 1

   • 'd' → count becomes 1

Final Map:

    { l: 1, e: 3, t: 1, c: 1, o: 1, d: 1 }

3. Finding the First Unique Character:

   • Looping with s.charAt(i):

     • At i = 0: s.charAt(0) is 'l' and its count is 1 → first unique character found.

   • The function returns index 0.

Thus, for the input "leetcode", the first unique character is 'l' at index 0.

---

🧠 What I Learned

Working on this problem reinforced the importance of hash-based counting for efficient lookups. I also learned how two distinct string access methods (toCharArray() and charAt(i)) can be effectively used in tandem to simplify problem-solving.

✅ Problem 3 – [Valid Anagram]

🛠️ Approach:

To determine whether two strings s and t are anagrams of each other, we use a frequency count array for lowercase English letters.

1. Initialize a frequency array of size 26 (because there are 26 letters from 'a' to 'z'):

    int[] freq = new int[26];
   

2. Populate the frequency array using the first string s:
   For each character c in s, convert it to an index using:

    idx = c - 'a';
    freq[idx]++;
   

   💡 Why c - 'a'?
   Characters in Java are internally represented by ASCII values. Subtracting 'a' (ASCII 97) from any lowercase letter gives us a unique index between 0 and 25.

   • Example: 'a' - 'a' = 0, 'b' - 'a' = 1, ..., 'z' - 'a' = 25.
     This maps each letter to a specific array index.

3. Adjust the frequency array using the second string t:
   For each character in t, subtract from the corresponding index:

     idx = c - 'a';
    freq[idx]--;
   

4. Final Validation:
   After processing both strings, loop through the freq array.
   If any value is not zero, it means the strings differ in character count → return false.
   If all values are zero → return true.

class Solution {
    public boolean isAnagram(String s, String t) {
    int []freq=new int[26];
    for(char c: s.toCharArray()){
        int idx=c-'a';
        freq[idx]=freq[idx]+1;
    }
    for(char c: t.toCharArray()){
        int idx=c-'a';
        freq[idx]=freq[idx]-1;
    }
    for(int i=0;i<26;i++){
        if(freq[i]!=0){
            return false;
        }
    }
    return true;
    }
}

📦 Physical Representation

Let’s take an example:

s = "anagram"
t = "nagaram"

Step 1: Frequency array after processing s

🔎 Each character in s increments its frequency at index c - 'a'.

Step 2: After processing t

All frequencies become 0 if t is a valid anagram.

---

🔡 Why idx = c - 'a'?

This expression maps a lowercase character 'a' to 'z' into the range 0 to 25:

• 'a' - 'a' = 0

• 'b' - 'a' = 1

• ...

• 'z' - 'a' = 25

This is useful for indexing the freq array directly without using a HashMap.

---

💡 Key Observations or Dry Run:

Let’s dry run for:

s = "anagram"
t = "nagaram"

After both loops:

• All character frequencies cancel out.

• freq array becomes all zeroes → ✅ valid anagram.

🧠 What I Learned:

Using a fixed-size array to count character frequencies is a simple and optimized way to solve anagram problems when inputs are limited to lowercase letters. This avoids extra space from a HashMap.

✅ Problem 4 – [Valid Palindrome]

🧠 Approach (Two-Pointer with Alphanumeric Filtering)

We use the two-pointer technique to compare characters from both ends of the string. Here's a breakdown of the steps:

---

🔁 Step-by-Step Logic:

1. Initialize two pointers:

   • i = 0 (start of the string)

   • j = s.length() - 1 (end of the string)

2. Skip non-alphanumeric characters:

   • If the character at index i is not alphanumeric, move i to the right.

   • If the character at index j is not alphanumeric, move j to the left.

   • This is handled by the helper method Alphanumeric(char c) which returns true if the character is a letter or digit.

3. Compare characters:

   • Convert both characters to lowercase using Character.toLowerCase().

   • If they don’t match, the string is not a palindrome → return false.

   • If they match, continue checking by moving i forward and j backward.

4. If all corresponding characters match, return true.

---

🔡 Alphanumeric Helper Function:

public boolean Alphanumeric(char c){
    return (c >= 'a' && c <= 'z') || 
           (c >= 'A' && c <= 'Z') || 
           (c >= '0' && c <= '9');
}

This function checks if the character is:

• A lowercase or uppercase letter

• A digit from 0–9

class Solution {
    public boolean Alphanumeric(char c){
        return (c>='a' && c<='z')||(c>='A' && c<='Z')||(c>='0'&&c<='9');
    }
    public boolean isPalindrome(String s) {
        int i=0;
        int j=s.length()-1;
        while(i<j){
            char c1=s.charAt(i);
            char c2=s.charAt(j);
            if(!Alphanumeric( c1)){
                i=i+1;
                continue;
            }
             if(!Alphanumeric( c2)){
                j=j-1;
                continue;
            }
            if(Character.toLowerCase(c1)!=Character.toLowerCase(c2)){
                return false;
            }
            i=i+1;
            j=j-1;
        }
        return true;
    }
}

📌 Physical Representation (Step-by-step Dry Run)

Let’s take the input string:
Input: "A man, a plan, a canal: Panama"

Step 1: Memory View of the String

---

Step 2: Two Pointer Movement (Skipping non-alphanumeric)

• i = 0, j = 29

  • s[i] = 'A', s[j] = 'a' → ✅ Equal (case-insensitive) → move inward

• i = 1, s[i] = ' ' → ❌ skip

• i = 2, s[i] = 'm', j = 28, s[j] = 'm' → ✅

• i = 3, s[i] = 'a', j = 27, s[j] = 'a' → ✅

• i = 4, s[i] = 'n', j = 26, s[j] = 'n' → ✅

• i = 5, s[i] = ',' → ❌ skip

• i = 6, s[i] = ' ', ❌ skip

• i = 7, s[i] = 'a', j = 25, s[j] = 'a' → ✅

• i = 8, s[i] = ' ', ❌ skip

• i = 9, s[i] = 'p', j = 24, s[j] = 'P' → ✅

• … and so on …

All characters match when skipping non-alphanumeric ones, so it returns true.

---

✅ Final Note:

• This physical walk-through demonstrates how we’re not removing characters from the string.

• We simply ignore non-alphanumeric characters on-the-fly using the helper function.

🧠 What I Learned

I learned how to use the two-pointer technique to check for palindromes efficiently, while also handling non-alphanumeric characters and case sensitivity — all without extra space.

Problem 5 – [String to Integer (atoi)]

Example 1:

Input: s = "42"

Output: 42

Explanation:

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^

Example 2:

Input: s = " -042"

Output: -42

Explanation:

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

Example 3:

Input: s = "1337c0d3"

Output: 1337

Explanation:

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
         ^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
             ^

Example 4:

Input: s = "0-1"

Output: 0

Explanation:

Step 1: "0-1" (no characters read because there is no leading whitespace)
         ^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
          ^

Example 5:

Input: s = "words and 987"

Output: 0

Explanation:

Reading stops at the first non-digit character 'w'.

Constraints:

• 0 <= s.length <= 200

• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

🚀 Approach

We need to convert a string into a 32-bit signed integer (int), following these specific rules (just like the atoi function in C/C++):

1. Ignore leading whitespaces:
   Use a loop to skip all spaces until we reach a non-space character.

2. Check for sign:
   If the next character is + or -, we store the sign accordingly (+1 or -1).

3. Convert digits:
   Keep converting digits one-by-one using num = num * 10 + digit.

4. Edge case - Overflow Handling:
   To avoid overflow while building the number, we:

   • Check if num > Integer.MAX_VALUE / 10 (i.e., multiplication itself will overflow)

   • Or if num == Integer.MAX_VALUE / 10 and the next digit is too big (>=7 for positive, >=8 for negative)

   • In both cases, we return Integer.MAX_VALUE or Integer.MIN_VALUE.

5. Return Final Answer:
   Multiply the result with the sign and return.

class Solution {
    public boolean isDigit(char c){
        return (c>='0' && c<='9');
    }
    public int myAtoi(String s) {
       //remove whitespace
       int i=0;
       int sign=1;
       int num=0;
       while(i<s.length() && s.charAt(i)==' ') {
            i=i+1;
        }


    //Signedness
    if(i<s.length()){
        if(s.charAt(i)=='-'){
            sign=-1;
            i=i+1;
        }
        else if(s.charAt(i)=='+'){
            sign=1;
            i=i+1;
        }
    }

    //conversion
    while(i<s.length() && isDigit(s.charAt(i))){
        int digit=s.charAt(i)-'0';

    //rounding 
    if(num==Integer.MAX_VALUE/10){
        if(sign==1){
            if(digit>=7){
                return Integer.MAX_VALUE;
            }
        }
            else if(sign==-1){
                if(digit>=8){
                    return Integer.MIN_VALUE;
                }
            }
        }
    if(num>Integer.MAX_VALUE/10){
        if(sign==1){
        return Integer.MAX_VALUE;
    }
    else{
        return Integer.MIN_VALUE;
    }
    }
    num=num*10+digit;
    i=i+1;
    }
    return sign*num;
       }
    }

---

📦 Physical Representation (Dry Run)

Let’s dry run the input:
Input: " -91283472332"

1. After Skipping Spaces:
   s = "-91283472332"
i = 3, sign = -1, num = 0

2. Conversion Steps:

Final Output: -2147483648

---

💡 Why We Did digit = s.charAt(i) - '0'?

We subtract '0' (ASCII value of 48) from any digit character to get its actual integer value.

Example:

• '3' - '0' = 51 - 48 = 3
  This trick converts characters like '7' directly into their numeric form.

---

🧠 What I Learned

I learned how to carefully handle edge cases like:

• Skipping whitespaces

• Managing signs

• Checking for overflow before it happens This problem taught me the importance of validating every step in input parsing logic.

✅ Conclusion

Day 4 of my 90 Days DSA Challenge was all about mastering string manipulation problems. From reversing integers and identifying the first unique character, to validating anagrams, checking for palindromes, and converting strings to integers — each problem helped me think more deeply about edge cases, ASCII value tricks, and input parsing techniques.

These problems may seem simple at first glance, but they build the foundation for handling real-world input validation, data cleaning, and low-level logic design. With every line of code, I’ve become more confident in breaking down problems and thinking through them with a structured approach.

On to Day 5 with more energy and curiosity! 🚀