Java || 20ms 100% || Intertwined linked lists. Reduce string before processing.
Basic algorithm:\n1. Copy the string to an array of characters.\n\n2. Scan string to count \'\\' characters.  Reduce string when possible.\n\t1. If no \'\\' in 
**Basic algorithm:**\n1. Copy the string to an array of characters.\n\n2. Scan string to count \'\\*\' characters.  Reduce string when possible.\n\t1. If no \'\\*\' in the string, then return original string.\n\t2. If string is half \'\\*\'s, then all characters will be deleted, so return empty string.\n\t3. If any \'\\*\' has half of the characters being \'\\*\'s, from beginning of string through that \'\\*\', then all those characters will be deleted, so `start` the processing from just after that \'\\*\'.\n3. Scan characters of copied string previously calculated `start` of processing to end of string.\n\t1. If \'\\*\' char found, then delete the \'\\*\' and the most recently scanned lowest valued letter in the string.  Delete characters by setting characters in copied string to zero.  Remove the deleted letter from its linked list.\n\t2. Else a letter character, so add that letter to its linked list, and set the head of that letter\'s linked list to the letter in the string.\n\n4. Compress the copied string by removing the zeroes (deleted characters), and return the result as a String.\n\n**Quickly locating rightmost of each letter using intertwined linked lists:**\nEach possible letter \'a\' to \'z\', has its own linked list containing the indexes within the string of that letter, going backward in the string.  All 26 of these linked lists are stored intertwined within a single `int[] linkedLists` array of the same length as the string.  The heads of these 26 linked lists are stored in the `int[] heads` array.\n\nThe diagram below, for the string "**aabba\\***", shows the relationships of the string, `linkedLists[]`, and `heads[]`, after scanning through the string and reaching the \'\\*\' character.  Linked lists have been created for the letters \'a\' and \'b\'.\n\nAlso with the diagram below, for deleting the \'\\*\' along with deleting the lowest-valued previous letter, the \'\\*\' at index 5 is replaced with a zero in the copied string.  And `heads[\'a\']` is 4, so the \'a\' at index 4 in the copied string is also replaced with a zero.  After deleting the \'a\' at index 4, the linked list for the letter \'a\' is updated by replacing `heads[\'a\']` with `linkedLists[heads[\'a\']]`, which removes the deleted \'a\' from the linked list for the letters \'a\'.\n```\n                  0     1     2     3     4     5\n\t\t\t\t___________________________________\nString:          \'a\'   \'a\'   \'b\'   \'b\'   \'a\'   \'*\'\n\n                    /<\\   /<-----------\\\n                   /   \\ /     /<--\\    \\\nlinkedLists[]:   -1     0    -1     2     1     ?\n                                    ^     ^\n\t\t\t\t                    |     |\n          +-------------------------|---->^\n          |  +--------------------->^\n\t\t  |  |\nheads[]:  4  3 -1 -1 -1 -1  ... -1 -1 -1 -1\n         ___________________________________\n      ... a  b  c  d  e  f  ...  w  x  y  z ...\n```\nAfter deleting the \'\\*\' and the \'a\' at index 4::\n```\n                  0     1     2     3     4     5\n\t\t\t\t___________________________________\nString:          \'a\'   \'a\'   \'b\'   \'b\'    0     0\n\n                   /<--\\       /<--\\\nlinkedLists[]:   -1     0    -1     2     1     ?\n                        ^           ^\n\t\t\t\t        |           |\n          +------------>^           |\n          |  +--------------------->^\n\t\t  |  |\nheads[]:  1  3 -1 -1 -1 -1  ... -1 -1 -1 -1\n         ___________________________________\n      ... a  b  c  d  e  f  ...  w  x  y  z ...\n```\n\n\n\n\n**--- Java code, with better coding practices ---**\n--- Runtime: 21ms to 22ms June 2024 ---\n```\nclass Solution {\n    public String clearStars(String s) {\n        int n = s.length();\n        char[] sc = s.toCharArray();\n\n        // Scan the string to get count of asterisks in the \n        // string.  When encountering an asterisk, if half of \n        // the characters from that asterisk back to the \n        // beginning of the string are asterisks, then the string \n        // from the start through that asterisk have an equal \n        // number of letters and asterisks, so that all of the \n        // characters up through that asterisk will be deleted, \n        // so set the start index for processing the string to \n        // the index after that asterisk.\n        //\n        // If no asterisks in the string, then return the string \n        // itself.  If exactly half of the characters in the \n        // string are asterisks, then the entire string will be \n        // deleted so return the empty string.\n        int start = 0;\n        int asteriskCount = 0;\n        for (int i = 0; i < n; i++) {\n            if (sc[i] == \'*\') {\n                asteriskCount++;\n                if (asteriskCount == ((i + 2) >> 1)) \n                    start = i + 1;\n            }\n        }\n        if (asteriskCount == 0)  return s;\n        if (start == n)  return "";\n        \n        // Remove \'*\' characters and rightmost lowest characters.\n        // Set character values to zero to mark as deleted.\n        // The array linkedLists[] contains linked lists, which \n        // are indexes into linkedLists[] of the previous \n        // occurrence of the same letter, or a -1 if no previous \n        // occurrence.  The array heads[] is indexed to the start \n        // of the letter\'s linked list in the linkedLists[] array.  \n        // The heads[] array references the rightmost (most recent) \n        // occurence of that letter, or -1 is no occurrences of \n        // that letter.\n        int[] linkedLists = new int[n];\n        int[] heads = new int[128];\n        for (int i = \'a\'; i <= \'z\'; i++)  heads[i] = -1;\n        for (int idx = start; idx < n; idx++) {\n            int c = sc[idx];\n            if (c == \'*\') {\n                if (idx >= n)  break;\n                sc[idx] = 0;\n                for (int i = \'a\'; i <= \'z\'; i++) {\n                    if (heads[i] >= 0) {\n                        sc[heads[i]] = 0;  // Remove a letter from links.\n                        heads[i] = linkedLists[heads[i]];\n                        break;\n                    }\n                }\n            } else {\n                linkedLists[idx] = heads[c];   // Add a letter to links.\n                heads[c] = idx;\n            }\n        }\n        \n        // Build the result string by removing deleted characters \n        // and collapsing the string.  Deleted chars were set to \n        // zero to mark that they were deleted.\n        int outIdx = 0;\n        for (int i = start; i < n; i++)\n            if (sc[i] != 0)\n                sc[outIdx++] = sc[i];\n        \n        return new String(sc, 0, outIdx);\n    }\n}\n```\n**--- Java Code, with faster runtime, but poorer coding practices ---**\n--- Runtime: 20ms to 21ms June 2024 ---\nThe poorer coding practices include using a deprecated form of `getBytes`, converting string characters to `byte` which does not handle unicode, and loop termination that relies on error-free passed values (i.e. the passed string MUST be well formed).  But sometimes work projects need speed to meet requirements, especially in real-time device-control programming, so that better programming practices may have to be sacrificed to meet the timing requirements.\n```\nclass Solution {\n    public String clearStars(String s) {\n        int n = s.length();\n        byte[] sc = new byte[n + 1];\n        s.getBytes(0, n, sc, 0);\n        sc[n] = \'*\';    // Extra \'*\' past end of string so no\n                        //   limit checking needed in FOR loop.\n        \n        // Scan the string to get count of asterisks in the \n        // string.  When encountering an asterisk, if half of \n        // the characters from that asterisk back to the \n        // beginning of the string are asterisks, then the string \n        // from the start through that asterisk have an equal \n        // number of letters and asterisks, so that all of the \n        // characters up through that asterisk will be deleted, \n        // so set the start index for processing the string to \n        // the index after that asterisk.\n        //\n        // If no asterisks in the string, then return the string \n        // itself.  If exactly half of the characters in the \n        // string are asterisks, then the entire string will be \n        // deleted so return the empty string.\n        int start = 0;\n        int asteriskCount = 0;\n        for (int i = 0; i < n; i++) {\n            if (sc[i] == \'*\') {\n                asteriskCount++;\n                if (asteriskCount == ((i + 2) >> 1)) \n                    start = i + 1;\n            }\n        }\n        if (asteriskCount == 0)  return s;\n        if (start == n)  return "";\n        \n        // Remove \'*\' characters and rightmost lowest characters.\n        // Set character values to zero to mark as deleted.\n        // The array linkedLists[] contains linked lists, which \n        // are indexes into linkedLists[] of the previous \n        // occurrence of the same letter, or a -1 if no previous \n        // occurrence.  The array heads[] is indexed to the start \n        // of the letter\'s linked list in the linkedLists[] array.  \n        // The heads[] array references the rightmost (most recent) \n        // occurence of that letter, or -1 is no occurrences of \n        // that letter.\n        int[] linkedLists = new int[n];\n        int[] heads = new int[128];\n        for (int i = \'a\'; i <= \'z\'; i++)  \n            heads[i] = -1;\n        for (int idx = start; ; idx++) {\n            int c = sc[idx];\n            if (c == \'*\') {\n                if (idx >= n)  break;\n                sc[idx] = 0;\n                for (int i = \'a\'; ; i++) {\n                    if (heads[i] >= 0) {\n                        sc[heads[i]] = 0;  // Remove a letter from links.\n                        heads[i] = linkedLists[heads[i]];\n                        break;\n                    }\n                }\n            } else {\n                linkedLists[idx] = heads[c];     // Add a letter to links.\n                heads[c] = idx;\n            }\n        }\n        \n        // Build the result string by removing deleted characters \n        // and collapsing the string.  Deleted chars were set to \n        // zero to mark that they were deleted.\n        int outIdx = 0;\n        for (int i = start; i < n; i++)\n            if (sc[i] != 0)\n                sc[outIdx++] = sc[i];\n        \n        return new String(sc, 0, outIdx);\n    }\n}\n```
['Java']