Why does the immutability of strings in java cause extra runtime for this problem: https://leetcode.com/problems/search-suggestions-system/solution/

Question

For this problem: https://leetcode.com/problems/search-suggestions-system/solution/, solution 1 states that for Java, _"there is an additional complexity of O(m^2) due to Strings being immutable, here m is the length of searchWord.") I am really scratching my head about this. Why the heck does immutability of string cause an additional runtime of O(m^2)?

Edit: I am trying to solve a Trie problem which involves creating a trie of words which are represented by character nodes ('c' -> 'a' -> 't'), and then searching for a word. When searching for a word, it is claimed that it takes an extra O(m^2) time in Java due to the immutability of strings in that language. Here is the solution provided by the website LeetCode:

// Custom class Trie with function to get 3 words starting with given prefix
class Trie {

    // Node definition of a trie
    class Node {
        boolean isWord = false;
        List<Node> children = Arrays.asList(new Node[26]);
    };
    Node Root, curr;
    List<String> resultBuffer;

    // Runs a DFS on trie starting with given prefix and adds all the words in the resultBuffer, limiting result size to 3
    void dfsWithPrefix(Node curr, String word) {
        if (resultBuffer.size() == 3)
            return;
        if (curr.isWord)
            resultBuffer.add(word);

        // Run DFS on all possible paths.
        for (char c = 'a'; c <= 'z'; c++)
            if (curr.children.get(c - 'a') != null)
                dfsWithPrefix(curr.children.get(c - 'a'), word + c);
    }
    Trie() {
        Root = new Node();
    }

    // Inserts the string in trie.
    void insert(String s) {

        // Points curr to the root of trie.
        curr = Root;
        for (char c : s.toCharArray()) {
            if (curr.children.get(c - 'a') == null)
                curr.children.set(c - 'a', new Node());
            curr = curr.children.get(c - 'a');
        }

        // Mark this node as a completed word.
        curr.isWord = true;
    }
    List<String> getWordsStartingWith(String prefix) {
        curr = Root;
        resultBuffer = new ArrayList<String>();
        // Move curr to the end of prefix in its trie representation.
        for (char c : prefix.toCharArray()) {
            if (curr.children.get(c - 'a') == null)
                return resultBuffer;
            curr = curr.children.get(c - 'a');
        }
        dfsWithPrefix(curr, prefix);
        return resultBuffer;
    }
};
class Solution {
    List<List<String>> suggestedProducts(String[] products,
                                         String searchWord) {
        Trie trie = new Trie();
        List<List<String>> result = new ArrayList<>();
        // Add all words to trie.
        for (String w : products)
            trie.insert(w);
        String prefix = new String();
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            result.add(trie.getWordsStartingWith(prefix));
        }
        return result;
    }
};

But to me it seems like instead of incrementing the string "prefix" one char at a time, and then searching through the trie for "prefix", I can instead iterate through the nodes of the trie one node at a time, and get the search suggestions from each node. This will completely remove the need to increment a "prefix" string, and from what I can tell will run in O(m) time for the search function (I'm not confused about the time required to build the trie). My solution is below. (Why) am I wrong?

class Solution {
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        root = new TrieNode();
        
        for( String each: products )
        {
            insert( each, root, 0 );
        }
        
        List<List<String>> sol = search( root, searchWord );
        
        return sol;
    }
    
    public void insert( String str, TrieNode curr, int pos )
    {
        if( pos >= str.length() ) return;
        
        if( !curr.map.containsKey( str.charAt(pos) ) )
        {
            TrieNode next = new TrieNode();
            
            curr.map.put( str.charAt(pos), next );
            
            curr = next;
        }
        else
        {
            curr = curr.map.get( str.charAt(pos) );
        }
        
        curr.strings.add( str );
        
        insert( str, curr, pos + 1 );
    }
    
    public List<List<String>> search( TrieNode curr, String s )
    {
        List<List<String>> sol = new ArrayList<>();
        
        boolean notFound = false;
        
        for( int i = 0; i < s.length(); i++ )
        {
            List<String> row = new ArrayList<>();
            
            if( notFound || !curr.map.containsKey( s.charAt(i) ) )
            {
                notFound = true;
                
                sol.add( row );
                continue;
            }
            else
            {
                curr = curr.map.get( s.charAt(i) );
                
                List<String> strs = curr.strings;
                
                
                
                Collections.sort( strs );
                
                for( int c = 0; c < Math.min( 3, strs.size() ); c++ )
                {
                    row.add( strs.get(c) );
                }
                
                sol.add( row );
                
                
            }
        }
        
        return sol;
    }
}

class TrieNode {
    
    List<String> strings;
    Map<Character, TrieNode> map;
    
    public TrieNode() {
        strings = new ArrayList<>();
        map = new HashMap<>();
    }
}

Answer 1

As comments mention please read How to Ask, if your question doesn't include code with out us scrolling through external resources it will likely be closed. The link is okay to have, just include code snippits, or sources that you have used.
To answer your question, every time you concatenate a string it is done in O(N) time as a new String has to be created with every concatenation, source.
So in the solution:

for (char c : searchWord.toCharArray()) {
    prefix += c;
    ...
}

Since you concatenate N times at O(N) time each, you add O(N^2) time complexity, as opposed to a language like C++ where string concatenation time complexity is based on an array growth (which could be linear if a growth has to happen every time, but will in most cases be constant time).

Answer 2

Let's consider how long it would take to build up the word "hello" one character at a time:

h
he
hel
hell
hello

Because Strings are immutable, at every step you need to start from scratch. For example, to build the last string, you can't just append "o" to the second-to-last: you need to first copy all those previous letters and then add the "o": h-e-l-l-o.

So, in that block of hello substrings above, each letter is one operation (to add it to that respective string copy).

From there, there are multiple ways to analyze that and realize it's n². One visual approach is to note that the characters form a triangle, with a base and height of n. The area of that triangle is half the area of its bounding box: n²/2, or 0.5n². Since O-notation ignores coefficients, this is n².