fork(3) download
copy 
  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #define NO_OF_CHARS 256
  4.  
  5. int min(int a, int b);
  6.  
  7. int longestUniqueSubsttr(char *str)
  8. {   int max_i=0;
  9.     int n = strlen(str);
  10.     int cur_len = 1;  // To store the lenght of current substring
  11.     int max_len = 1;  // To store the result
  12.     int prev_index;  // To store the previous index
  13.     int i;
  14.     int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
  15.     char *s;
  16.  
  17.     /* Initialize the visited array as -1, -1 is used to indicate that
  18.        character has not been visited yet. */
  19.     for (i = 0; i < NO_OF_CHARS;  i++)
  20.         visited[i] = -1;
  21.  
  22.     /* Mark first character as visited by storing the index of first
  23.        character in visited array. */
  24.     visited[str[0]] = 0;
  25.  
  26.     /* Start from the second character. First character is already processed
  27.        (cur_len and max_len are initialized as 1, and visited[str[0]] is set */
  28.     for (i = 1; i < n; i++)
  29.     {
  30.         prev_index =  visited[str[i]];
  31.  
  32.         /* If the currentt character is not present in the already processed
  33.            substring or it is not part of the current NRCS, then do cur_len++ */
  34.         if (prev_index == -1 || i - cur_len > prev_index)
  35.             cur_len++;
  36.  
  37.         /* If the current character is present in currently considered NRCS,
  38.            then update NRCS to start from the next character of previous instance. */
  39.         else
  40.         {
  41.             /* Also, when we are changing the NRCS, we should also check whether
  42.               length of the previous NRCS was greater than max_len or not.*/
  43.             if (cur_len > max_len)
  44.                 {max_len = cur_len;
  45.                 if(prev_index!=-1)
  46.                 max_i=prev_index;
  47.                 }
  48.  
  49.             cur_len = i - prev_index;
  50.         }
  51.  
  52.         visited[str[i]] = i; // update the index of current character
  53.     }
  54.  
  55.     // Compare the length of last NRCS with max_len and update max_len if needed
  56.     if (cur_len > max_len)
  57.        { max_len = cur_len;
  58.            if(prev_index!=-1)
  59.                 max_i=prev_index;
  60.        }
  61.  
  62.  
  63.     free(visited); // free memory allocated for visited
  64. s=&str[max_i];
  65. i=0;
  66. while(i<max_len)
  67. {
  68.     printf("%c",*s);
  69.     i++;
  70.     *s++;
  71. }
  72. printf("\n");
  73.     return max_len;
  74. }
  75.  
  76. /* A utility function to get the minimum of two integers */
  77. int min(int a, int b)
  78. {
  79.     return (a>b)?b:a;
  80. }
  81.  
  82. /* Driver program to test above function */
  83. int main()
  84. {
  85.     char str[] = "GEEKSFORGEEKS";
  86.     printf("The input string is %s \n", str);
  87.     int len =  longestUniqueSubsttr(str);
  88.     printf("The length of the longest non-repeating character substring is %d", len);
  89.  
  90.     getchar();
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The input string is GEEKSFORGEEKS 
EKSFORG
The length of the longest non-repeating character substring is 7
https://ideone.com/FFQRkw
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!