Day 7 of DSA: String

What are Strings?

Strings can be considered as a collection of characters. In Java, Strings are objects of the String class, unlike primitive data types. One of the most important characteristics of Strings in Java is that they are immutable, meaning once created, they cannot be changed.

When we talk about Strings in Java, we need to understand two fundamental concepts:

1. String Constant Pool
2. Immutability

String Constant Pool

The String Constant Pool (SCP) is a special memory region in the Java heap that stores string literals. When multiple objects have the same string literal, those objects point to the same reference in the string pool. This design helps in:

• Memory optimization: Avoids duplicate string storage
• Performance: String comparison becomes faster
• Security: Prevents unintended modifications

String Creation Methods

Method 1: String Literal

String n1 = "Kabilesh";
String n2 = "Kabilesh";
System.out.println(n1 == n2);        // Output: true
System.out.println(n1.equals(n2));   // Output: true

In this case, both n1 and n2 point to the same object in the String pool.

Method 2: Using new keyword

String s1 = new String("Kabilesh");
String s2 = new String("Kabilesh");

System.out.println(s1 == s2);        // Output: false
System.out.println(s1.equals(s2));   // Output: true

Here, two separate objects are created in the heap memory, even though they have the same value.

Understanding == vs .equals()

• == : Checks whether two reference variables point to the same object in memory
• .equals() : Checks whether the actual content/values are the same

How String Pool Works Internally

When you create a string using a literal like String s1 = "java dsa":

1. JVM checks if “java dsa” already exists in the String pool
2. If it exists, s1 references that existing object
3. If it doesn’t exist, a new string object is created in the pool and s1 references it

String str1 = "Hello";          // Created in String pool
String str2 = "Hello";          // References same object in pool
String str3 = new String("Hello"); // New object in heap (outside pool)
String str4 = str3.intern();    // Returns reference from pool

System.out.println(str1 == str2);    // true (same reference)
System.out.println(str1 == str3);    // false (different locations)
System.out.println(str1 == str4);    // true (intern() returns pool reference)

String Immutability

Once a String object is created, its value cannot be modified. Any operation that seems to modify a string actually creates a new string object.

String name = "Kabil";
name = name + "esh";  // Creates a new String object "Kabilesh"
// Original "Kabil" still exists in memory (if referenced elsewhere)

Why are Strings Immutable?

1. Security: String parameters cannot be modified after being passed
2. Thread Safety: Immutable objects are inherently thread-safe
3. Caching: String pool is possible because of immutability
4. Hash Code Caching: Hash codes can be cached as they won’t change

   How String Works Internally

Internally, a String is stored as a character array (char[] in Java 8 and earlier, byte[] in Java 9+).

// Internal representation (simplified)
public final class String {
    private final char[] value;  // Java 8
    // private final byte[] value;  // Java 9+
    
    private int hash;  // Cached hash code
    
    // Constructor
    public String(String original) {
        this.value = original.value;
        this.hash = original.hash;
    }
}

Key points:

• The final keyword on the class prevents subclassing
• The final keyword on the value array prevents reassignment
• The array itself is private, preventing external modification

Common String Methods

String text = "Java Programming";

// Length
System.out.println(text.length());              // 16

// Character at index
System.out.println(text.charAt(0));             // J

// Substring
System.out.println(text.substring(5));          // Programming
System.out.println(text.substring(5, 9));       // Prog

// Contains
System.out.println(text.contains("Program"));   // true

// Index of
System.out.println(text.indexOf("a"));          // 1
System.out.println(text.lastIndexOf("a"));      // 3

// Replace
System.out.println(text.replace("Java", "Python")); // Python Programming

// Case conversion
System.out.println(text.toLowerCase());         // java programming
System.out.println(text.toUpperCase());         // JAVA PROGRAMMING

// Trim whitespace
String spaces = "  Hello  ";
System.out.println(spaces.trim());              // Hello

// Split
String[] words = text.split(" ");
System.out.println(Arrays.toString(words));     // [Java, Programming]

// Comparison
System.out.println(text.equals("Java Programming"));      // true
System.out.println(text.equalsIgnoreCase("java programming")); // true
System.out.println(text.compareTo("Java"));               // positive value

// Check empty
String empty = "";
System.out.println(empty.isEmpty());            // true
System.out.println(empty.isBlank());            // true (Java 11+)

// StartsWith and EndsWith
System.out.println(text.startsWith("Java"));    // true
System.out.println(text.endsWith("ming"));      // true

String Formatting & toString() Methods

String Formatting

String formatting allows you to create formatted strings with placeholders.

// Using String.format()
String name = "Kabilesh";
int age = 25;
double height = 5.9;

String formatted = String.format("Name: %s, Age: %d, Height: %.1f", name, age, height);
System.out.println(formatted);  // Name: Kabilesh, Age: 25, Height: 5.9

// Format specifiers
System.out.println(String.format("%d", 42));           // 42 (integer)
System.out.println(String.format("%f", 3.14159));      // 3.141590 (float)
System.out.println(String.format("%.2f", 3.14159));    // 3.14 (2 decimals)
System.out.println(String.format("%s", "Hello"));      // Hello (string)
System.out.println(String.format("%10s", "Hi"));       // "        Hi" (right-aligned)
System.out.println(String.format("%-10s", "Hi"));      // "Hi        " (left-aligned)

// Using printf (prints directly)
System.out.printf("Value: %d%n", 100);

toString() Method

The toString() method converts an object to its string representation.

class Student {
    String name;
    int rollNo;
    
    public Student(String name, int rollNo) {
        this.name = name;
        this.rollNo = rollNo;
    }
    
    @Override
    public String toString() {
        return "Student{name='" + name + "', rollNo=" + rollNo + "}";
    }
}

Student student = new Student("Kabilesh", 101);
System.out.println(student.toString());  // Student{name='Kabilesh', rollNo=101}
System.out.println(student);             // Same as above (implicitly calls toString())

// Built-in types
System.out.println(Integer.toString(42));       // "42"
System.out.println(Double.toString(3.14));      // "3.14"
System.out.println(Arrays.toString(new int[]{1, 2, 3})); // [1, 2, 3]

StringBuilder

StringBuilder is a mutable sequence of characters. Unlike String, StringBuilder can be modified without creating new objects, making it more efficient for string manipulation operations.

Key Features:

• Mutable: Can be modified after creation
• Not thread-safe: Faster but not synchronized
• Better performance: For concatenation and modifications

Common StringBuilder Operations

StringBuilder sb = new StringBuilder("Hello");

// Append
sb.append(" World");
System.out.println(sb);                  // Hello World

// Insert
sb.insert(5, ",");
System.out.println(sb);                  // Hello, World

// Delete
sb.delete(5, 6);
System.out.println(sb);                  // Hello World

// DeleteCharAt
sb.deleteCharAt(5);
System.out.println(sb);                  // HelloWorld

// Replace
sb.replace(0, 5, "Hi");
System.out.println(sb);                  // HiWorld

// Reverse
sb.reverse();
System.out.println(sb);                  // dlroWiH
sb.reverse();                            // Reverse back

// Set character at index
sb.setCharAt(0, 'h');
System.out.println(sb);                  // hiWorld

// Capacity
StringBuilder sb2 = new StringBuilder();
System.out.println(sb2.capacity());      // 16 (default)

StringBuilder sb3 = new StringBuilder(50);
System.out.println(sb3.capacity());      // 50

// Convert to String
String result = sb.toString();

When to Use StringBuilder?

• String concatenation in loops
• Building dynamic strings
• Frequent string modifications
• Performance-critical applications

// Bad practice - creates many String objects
String result = "";
for (int i = 0; i < 1000; i++) {
    result += i;  // Creates 1000 new String objects (very slow!)
}

// Good practice - uses StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
    sb.append(i);  // Modifies same object (fast!)
}
String result = sb.toString();

StringBuffer

StringBuffer is similar to StringBuilder but with one key difference: it’s thread-safe (synchronized).

Key Features:

• Mutable: Can be modified after creation
• Thread-safe: All methods are synchronized
• Slower than StringBuilder: Due to synchronization overhead
• Legacy class: Introduced in Java 1.0

Common StringBuffer Operations

StringBuffer sbf = new StringBuffer("Java");

// All StringBuilder methods work the same
sbf.append(" Programming");
System.out.println(sbf);                 // Java Programming

sbf.insert(0, "Learning ");
System.out.println(sbf);                 // Learning Java Programming

sbf.reverse();
System.out.println(sbf);                 // gnimmargorP avaJ gninraeL

sbf.reverse();
sbf.delete(0, 9);
System.out.println(sbf);                 // Java Programming

System.out.println(sbf.toString());

When to Use StringBuffer?

• Multi-threaded environments where multiple threads modify the same string
• When thread safety is required
• Legacy code (StringBuilder was introduced in Java 5 as a faster alternative)

Comparison: String vs StringBuilder vs StringBuffer

Feature	String	StringBuilder	StringBuffer
Mutability	Immutable	Mutable	Mutable
Thread Safety	Yes (immutable)	No	Yes (synchronized)
Performance	Slower for modifications	Fast	Slower than StringBuilder
Use Case	Fixed strings	Single-threaded modifications	Multi-threaded modifications
Storage	String pool + heap	Heap	Heap
Memory	Creates new objects	Modifies same object	Modifies same object
Since	Java 1.0	Java 5 (1.5)	Java 1.0

Performance Comparison Example

// Performance comparison
long startTime, endTime;

// Using String concatenation
startTime = System.currentTimeMillis();
String str = "";
for (int i = 0; i < 10000; i++) {
    str += "a";
}
endTime = System.currentTimeMillis();
System.out.println("String: " + (endTime - startTime) + "ms");

// Using StringBuilder
startTime = System.currentTimeMillis();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append("a");
}
endTime = System.currentTimeMillis();
System.out.println("StringBuilder: " + (endTime - startTime) + "ms");

// Using StringBuffer
startTime = System.currentTimeMillis();
StringBuffer sbf = new StringBuffer();
for (int i = 0; i < 10000; i++) {
    sbf.append("a");
}
endTime = System.currentTimeMillis();
System.out.println("StringBuffer: " + (endTime - startTime) + "ms");

// Typical output:
// String: 250-500ms (slowest)
// StringBuilder: 0-5ms (fastest)
// StringBuffer: 0-10ms (fast, but slower than StringBuilder)

Practice Problems

Problem 1: Palindrome Check

Check if a given string is a palindrome (reads the same forward and backward).

public static boolean isPalindrome(String str) {
    // Remove spaces and convert to lowercase
    str = str.replaceAll("\\s+", "").toLowerCase();
    
    int left = 0;
    int right = str.length() - 1;
    
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Test
System.out.println(isPalindrome("A man a plan a canal Panama")); // true
System.out.println(isPalindrome("racecar"));                     // true
System.out.println(isPalindrome("hello"));                       // false

Time Complexity: O(n)
Space Complexity: O(n) for the cleaned string

Problem 2: Reverse Words in a String

Reverse the order of words in a string.

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

// Test
System.out.println(reverseWords("Hello World Java")); // Java World Hello
System.out.println(reverseWords("DSA is fun"));       // fun is DSA

Time Complexity: O(n)
Space Complexity: O(n)

Problem 3: Count Character Frequency

Count the frequency of each character in a string.

public static void countCharacterFrequency(String str) {
    HashMap<Character, Integer> frequencyMap = new HashMap<>();
    
    for (char c : str.toCharArray()) {
        if (c != ' ') {  // Ignore spaces
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
    }
    
    for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }
}

// Test
countCharacterFrequency("hello world");
// Output: h:1, e:1, l:3, o:2, w:1, r:1, d:1

Time Complexity: O(n)
Space Complexity: O(k) where k is the number of unique characters

Problem 4: Anagram Check

Check if two strings are anagrams of each other.

public static boolean isAnagram(String str1, String str2) {
    // Remove spaces and convert to lowercase
    str1 = str1.replaceAll("\\s+", "").toLowerCase();
    str2 = str2.replaceAll("\\s+", "").toLowerCase();
    
    if (str1.length() != str2.length()) {
        return false;
    }
    
    char[] arr1 = str1.toCharArray();
    char[] arr2 = str2.toCharArray();
    
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    
    return Arrays.equals(arr1, arr2);
}

// Alternative approach using HashMap
public static boolean isAnagramHashMap(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }
    
    HashMap<Character, Integer> map = new HashMap<>();
    
    for (char c : str1.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    
    for (char c : str2.toCharArray()) {
        if (!map.containsKey(c) || map.get(c) == 0) {
            return false;
        }
        map.put(c, map.get(c) - 1);
    }
    
    return true;
}

// Test
System.out.println(isAnagram("listen", "silent"));   // true
System.out.println(isAnagram("hello", "world"));     // false

Time Complexity: O(n log n) for sorting approach, O(n) for HashMap approach
Space Complexity: O(n)

Problem 5: Remove Duplicates

Remove duplicate characters from a string while maintaining order.

public static String removeDuplicates(String str) {
    StringBuilder result = new StringBuilder();
    HashSet<Character> seen = new HashSet<>();
    
    for (char c : str.toCharArray()) {
        if (!seen.contains(c)) {
            seen.add(c);
            result.append(c);
        }
    }
    return result.toString();
}

// Test
System.out.println(removeDuplicates("programming")); // progamin
System.out.println(removeDuplicates("hello"));       // helo

Time Complexity: O(n)
Space Complexity: O(n)

Problem 6: First Non-Repeating Character

Find the first non-repeating character in a string.

public static char firstNonRepeating(String str) {
    HashMap<Character, Integer> frequencyMap = new HashMap<>();
    
    // Count frequencies
    for (char c : str.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }
    
    // Find first non-repeating
    for (char c : str.toCharArray()) {
        if (frequencyMap.get(c) == 1) {
            return c;
        }
    }
    return '\0'; // No non-repeating character
}

// Test
System.out.println(firstNonRepeating("leetcode"));      // l
System.out.println(firstNonRepeating("loveleetcode"));  // v
System.out.println(firstNonRepeating("aabb"));          // (null character)

Time Complexity: O(n)
Space Complexity: O(k) where k is the number of unique characters

Problem 7: Longest Substring Without Repeating Characters

Find the length of the longest substring without repeating characters.

public static int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char currentChar = s.charAt(right);
        
        if (map.containsKey(currentChar)) {
            left = Math.max(left, map.get(currentChar) + 1);
        }
        
        map.put(currentChar, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Test
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3 (abc)
System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1 (b)
System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3 (wke)

Time Complexity: O(n)
Space Complexity: O(min(n, m)) where m is the character set size

Problem 8: Valid Parentheses

Check if a string containing parentheses is valid.

public static boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<>();
    HashMap<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    
    for (char c : s.toCharArray()) {
        if (map.containsValue(c)) {
            // Opening bracket
            stack.push(c);
        } else if (map.containsKey(c)) {
            // Closing bracket
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

// Test
System.out.println(isValidParentheses("()"));       // true
System.out.println(isValidParentheses("()[]{}"));   // true
System.out.println(isValidParentheses("(]"));       // false
System.out.println(isValidParentheses("([)]"));     // false

Time Complexity: O(n)
Space Complexity: O(n)

Problem 9: String Compression

Compress a string by counting consecutive characters.

public static String compressString(String s) {
    if (s.length() <= 1) {
        return s;
    }
    
    StringBuilder compressed = new StringBuilder();
    int count = 1;
    
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            count++;
        } else {
            compressed.append(s.charAt(i - 1));
            if (count > 1) {
                compressed.append(count);
            }
            count = 1;
        }
    }
    
    // Append last character
    compressed.append(s.charAt(s.length() - 1));
    if (count > 1) {
        compressed.append(count);
    }
    
    // Return original if compression doesn't save space
    return compressed.length() < s.length() ? compressed.toString() : s;
}

// Test
System.out.println(compressString("aabcccccaaa")); // a2bc5a3
System.out.println(compressString("abc"));         // abc (no compression)
System.out.println(compressString("aabbcc"));      // aabbcc (no space saved)

Time Complexity: O(n)
Space Complexity: O(n)

Problem 10: Check String Rotation

Check if one string is a rotation of another.

public static boolean isRotation(String s1, String s2) {
    if (s1.length() != s2.length() || s1.length() == 0) {
        return false;
    }
    
    // If s2 is a rotation of s1, then s2 will be a substring of s1+s1
    String doubled = s1 + s1;
    return doubled.contains(s2);
}

// Test
System.out.println(isRotation("waterbottle", "erbottlewat")); // true
System.out.println(isRotation("hello", "lohel"));              // true
System.out.println(isRotation("hello", "world"));              // false

Time Complexity: O(n)
Space Complexity: O(n)

Key Takeaways

1. Strings are immutable - Any modification creates a new String object
2. String pool optimizes memory by reusing string literals
3. Use == for reference comparison and .equals() for value comparison
4. StringBuilder is best for single-threaded string manipulation
5. StringBuffer should be used in multi-threaded environments
6. Avoid string concatenation in loops - use StringBuilder instead
7. Common string operations: substring, replace, split, trim, indexOf
8. String problems often involve sliding window, two pointers, or hash maps
9. The .intern() method adds string to pool and returns pool reference
10. String formatting with String.format() and toString() for object representation

Best Practices

• Use String for immutable text
• Use StringBuilder for string manipulation in single-threaded code
• Use StringBuffer only when thread safety is needed
• Avoid + operator for concatenation in loops
• Use .equals() for string comparison, not ==
• Consider using String.format() or StringBuilder for building complex strings
• Be mindful of the performance implications of string operations
• Use appropriate data structures (HashMap, HashSet) for character/frequency problems
• Leverage two-pointer technique for palindrome and reversal problems
• Use sliding window for substring problems

Summary

Strings are one of the most commonly used data types in programming. Understanding their internal working, immutability, and the differences between String, StringBuilder, and StringBuffer is crucial for writing efficient code. Practice various string manipulation problems to strengthen your understanding of string algorithms and problem-solving techniques.

---

Next: Day 8 will cover Recursion - understanding recursive thinking and problem-solving!