Strings — Essential for Problem Solving

Day 2 of 15 Days of Data Structures and Algorithms

Photo by Adi Goldstein on Unsplash

What is a String?

A string is a sequence of characters. In Java, strings are objects of the String class and are immutable, meaning once a string is created, it cannot be changed.

Characteristics:

1. Immutable: Operations like concatenation or replacement create a new string object.
2. Zero-based Indexing: Similar to arrays, strings start indexing from 0.
3. Stored in String Pool: Java optimizes memory by storing strings in a pool for reuse.

Common Operations:

Concatenation: Combine two strings.

+ operator or concat() method.

Substring: Extract a part of the string.

substring(beginIndex, endIndex).

Length: Get the length of the string.

length() method.

Character Access: Access characters by index.

charAt(index).

Replace: Replace a character or substring.

replace() or replaceAll().

Split: Divide a string based on a delimiter.

split(regex).

Time and Space Complexities of String Operations:

• Concatenation: O(n) for String, O(1) for StringBuilder.
• Substring: O(n) for copying the substring.
• Search: O(n).
• Space Complexity: Depends on the operation (e.g., new strings created in concatenation).

Trade-offs and Use Cases:

• Use StringBuilder or StringBuffer for mutable strings to avoid creating multiple objects during operations.
• Use regular expressions (Pattern and Matcher classes) for complex string searches and replacements.

Common Mistakes:

1. Index Out of Bounds: Ensure indices are within the valid range (0 to string.length()-1).
2. Case Sensitivity: Java strings are case-sensitive by default.
3. Mutability Misunderstandings: Understand that String operations often create new objects.

Implementation in Java

Declaring and Initializing Strings:

// Declaration
String greeting = "Hello";

// Using new keyword
String name = new String("World");

// Concatenation
String message = greeting + ", " + name + "!";

Traversing a String:

String str = "Example";
for (int i = 0; i < str.length(); i++) {
    System.out.println(str.charAt(i));
}

// Using enhanced for-loop
for (char ch : str.toCharArray()) {
    System.out.println(ch);
}

Common Operations:

Reversing a String:

public String reverseString(String str) {
    StringBuilder reversed = new StringBuilder(str);
    return reversed.reverse().toString();
}

Checking for Palindrome:

public boolean isPalindrome(String str) {
    int start = 0, end = str.length() - 1;
    while (start < end) {
        if (str.charAt(start) != str.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Java-Specific Insights

StringBuilder vs StringBuffer:

• StringBuilder is faster but not thread-safe.
• StringBuffer is thread-safe but slower due to synchronization.

Regular Expressions:

• Use the Pattern and Matcher classes for complex searches.

Pattern pattern = Pattern.compile("\bhello\b");
Matcher matcher = pattern.matcher("hello world");
while (matcher.find()) {
    System.out.println("Found: " + matcher.group());
}

Comparing Strings:

• Use equals() for content comparison, not ==.
• Use compareTo() for lexicographical comparison.

Popular Interview Questions

1. Reverse Words in a String

Problem Statement: Given a string, reverse the order of words.

Solution:

public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder result = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        result.append(words[i]).append(" ");
    }
    return result.toString().trim();
}

2. Find the First Non-Repeating Character

Problem Statement: Given a string, find the first character that does not repeat.

Solution:

public char firstNonRepeatingChar(String s) {
    Map<Character, Integer> charCount = new HashMap<>();
    for (char c : s.toCharArray()) {
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    for (char c : s.toCharArray()) {
        if (charCount.get(c) == 1) {
            return c;
        }
    }
    return '_'; // Or any default value indicating no such character
}

Practice Questions

1. Check if two strings are anagrams of each other.
2. Count the number of vowels and consonants in a string.
3. Find the longest substring without repeating characters.
4. Check if a string can be rotated to form another string.
5. Count the occurrences of a word in a string.
6. Implement a function to check if a string contains only digits.
7. Convert a string to an integer without using Integer.parseInt().
8. Find all permutations of a given string.
9. Check if a string is a valid palindrome ignoring spaces and case.
10. Compress a string using the counts of repeated characters (e.g., “aabcc” -> “a2b1c2”).