Giải quyết số chuỗi con có hai nhân vật độc đáo trong thời gian O (n)

Question

Tôi đang làm việc trên một loạt các vấn đề chuỗi:

Cho một chuỗi:

1. Tìm các xâu chỉ chứa hai nhân vật duy nhất có độ dài tối đa.
2. Tìm số lượng tất cả các phần có chứa AT MOST hai ký tự duy nhất.
3. Tìm số lượng tất cả các phần tử có chứa hai ký tự duy nhất.

Có vẻ như vấn đề 1 và 2 có giải pháp O (n). Tuy nhiên tôi không thể nghĩ ra giải pháp O (n) cho vấn đề 3. (Here là giải pháp cho vấn đề 2 và here là vấn đề 1.).

Vì vậy, tôi muốn biết có một giải pháp O (n) cho vấn đề 3 tồn tại hay không?

Thêm mẫu đầu vào/đầu ra cho vấn đề 3:

Given: abbac

Return: 6

Bởi vì có 6 chuỗi chứa hai ký tự duy nhất: ab, abb, abba, BBA, ba, ac

Answer 1

• Đọc các ký tự của chuỗi theo thứ tự. Điền vào một mảng với các chỉ số của ký tự đầu tiên của mỗi lần chạy các ký tự liên tiếp, thời lượng chạy, và liệu ký tự đó có bằng ký tự thứ 2 trước đó gặp phải hay không. Gọi mảng này A. Theo dõi tổng số đang chạy và khởi tạo nó bằng không. gọi đây là x.

ví dụ, abbaabbccd => [(0,1, ), (1,2,), (3,2, T), (5,2, T), (7,2, F), (9,1, F)] = A

• Đối với mỗi chỉ số i trong A, tìm chỉ mục j bạn nhận được bằng cách di chuyển sang phải 1, sau đó tiếp tục di chuyển sang phải chừng nào bạn còn đất trên các yếu tố 'Đúng' của A.

ví dụ: nếu i = 0, thì j = 3 vì (5,2, T) là đúng, nhưng (7,2, F) là sai.

• Cho x = x + (A [i] [1]) * (Sum từ k = i + 1 tới j của A [k] [1])

ví dụ như, tiếp tục i = 0, chúng tôi nhận được 1 * 6 = 6. Điều này tương ứng với tất cả các chuỗi 6 'ab ...' bắt đầu bằng 'a'.

• Bây giờ, thời gian chạy là gì? Vâng, lưu ý ở bước 2, bạn tìm thấy j bằng cách di chuyển sang phải qua một loạt các phần tử thực sự cho đến khi bạn tìm thấy một phần tử sai. Yếu tố đó vẫn cố định cho đến khi i = j, tại thời điểm đó nó di chuyển sang phải một lần nữa. Chúng ta có hai chỉ số di chuyển đơn điệu về bên phải, do đó, việc xử lý A là tuyến tính trong A là tuyến tính trong đầu vào.

Để kết thúc ví dụ này: (bắt đầu với x = 0)

• i = 0, j = 3, x + = 6 -> x = 6
• i = 1, j = 3, x + = 8 -> x = 14
• i = 2, j = 3, x + = 4 -> x = 18
• i = 3, j = 4, x + = 4 -> x = 22
• i = 4, j = 5, x + = 2 -> x = 24

---

Tôi nên đề cập đến, bạn không tính tổng từ i + 1 đến j mỗi lần, bạn chỉ cần giảm số tiền theo số tiền thích hợp mỗi khi bạn tăng i và chỉ tính toán lại khi j tăng.

Answer 2

Tìm số lượng tất cả các phần tử có chứa hai ký tự duy nhất.

Chỉnh sửa: Tôi đã đọc sai câu hỏi. Giải pháp này phát hiện chuỗi con độc đáo với ít nhất 2 nhân vật độc đáo

1. Số chuỗi con cho một từ được có chiều dài là len được cho bởi len * (len + 1)/2

   sum = len * (len + 1)/2

   1. Chúng tôi đang tìm kiếm các chất nền có chiều dài lớn hơn 1. Công thức trên bao gồm các chất nền có chiều dài 1. Chúng ta cần phải trừ đi các chất nền đó.

Vì vậy, tổng số 2 chuỗi con với doanh nghiệp là len * (len + 1)/2 - l.

sum = `len * (len + 1)/2 - l` 

1. Tìm chạy dài liên tiếp của các nhân vật trong đó đều giống nhau. Áp dụng bước 1 và 2. Trừ số tiền hiện tại này khỏi số sum như được lấy từ bước 2.

Thực hiện mẫu sau.

public static int allUniq2Substrings(char s[]) { 
    int sum = s.length * (s.length + 1)/2 - s.length; 
    int sameRun = 0; 
    for (int i = 0, prev = -1; i < s.length; prev = s[i++]) { 
     if (s[i] != prev) { 
      sum -= sameRun * (sameRun + 1)/2 - sameRun; 
      sameRun = 1; 
     } else { 
      sameRun++; 
     } 
    } 

    return sum - (sameRun * (sameRun + 1)/2 - sameRun); 

} 

---

allUniq2Substrings("aaac".toCharArray()); 
3 

allUniq2Substrings("aabc".toCharArray()); 
5 

allUniq2Substrings("aaa".toCharArray()); 
0 

allUniq2Substrings("abcd".toCharArray()); 
6 

Sửa Hãy để tôi thử này một lần nữa. Tôi sử dụng các bất biến ở trên . Đây là một vấn đề con của việc tìm kiếm tất cả các chất nền có chứa ít nhất 2 ký tự duy nhất. Tôi có một phương pháp được đăng ở trên cung cấp cho tôi các chất nền độc đáo cho bất kỳ độ dài nào. Tôi sẽ sử dụng nó để tạo ra các chất nền từ một tập hợp chứa 2 ký tự duy nhất.

Chúng tôi chỉ cần theo dõi thời gian chạy dài nhất của các ký tự có độ dài được đặt là 2. nghĩa là Bất kỳ hoán vị nào của 2 ký tự duy nhất. Tổng số lần chạy như vậy sẽ cho chúng ta tổng số lượng chất nền mong muốn.

public static int allUniq2Substrings(char s[]) { 
    int sum = s.length * (s.length + 1)/2 - s.length; 
    int sameRun = 0; 
    for (int i = 0, prev = -1; i < s.length; prev = s[i++]) { 
     if (s[i] != prev) { 
      sum -= sameRun * (sameRun + 1)/2 - sameRun; 
      sameRun = 1; 
     } else { 
      sameRun++; 
     } 
    } 

    return sum - (sameRun * (sameRun + 1)/2 - sameRun); 

} 

public static int uniq2substring(char s[]) { 
    int last = 0, secondLast = 0; 
    int sum = 0; 
    for (int i = 1; i < s.length; i++) { 
     if (s[i] != s[i - 1]) { 
      last = i; 
      break; 
     } 
    } 

    boolean OneTwo = false; 
    int oneTwoIdx = -1; //alternating pattern 

    for (int i = last + 1; i < s.length; ++i) { 
     if (s[secondLast] != s[i] && s[last] != s[i]) { //detected more than 2 uniq chars 
      sum += allUniq2Substrings(Arrays.copyOfRange(s, secondLast, i)); 
      secondLast = last; 
      last = i; 
      if (OneTwo) { 
       secondLast = oneTwoIdx; 
      } 
      OneTwo = false; 
     } else if (s[i] != last) { //alternating pattern detected a*b*a 
      OneTwo = true; 
      oneTwoIdx = i; 
     } 

    } 

    return sum + allUniq2Substrings(Arrays.copyOfRange(s, secondLast, s.length)); 
} 

---

uniq2substring("abaac".toCharArray()) 
6 


uniq2substring("aab".toCharArray()) 
2 

uniq2substring("aabb".toCharArray()) 
4 

uniq2substring("ab".toCharArray()) 
1 

Answer 3

Tôi nghĩ vào liên kết đăng bởi bạn cho các giải pháp của vấn đề 2

http://coders-stop.blogspot.in/2012/09/directi-online-test-number-of.html

thể chúng ta rất dễ dàng được mô hình cho các giải pháp của vấn đề thứ ba là tốt. Chỉ việc điều chỉnh chương trình điều khiển như dưới

int numberOfSubstrings (string A) { 
    int len = A.length(); 
    int res = 0, j = 1, c = 1, a[2][2]; 
    a[0][0] = A[0]; a[0][1] = 1; 
    for(int i=0;i<len;i++) { 
     >>int start = -1; 
     for (;j<len; j++) { 

      c = isInArray(a, c, A[j]); 
      >> if (c == 2 && start != - 1) start = j; 
      if(c == -1) break; 
     } 
     >>c = removeFromArray(a,A[i]); 
     res = (res + j - start); 
    } 
    return res; 
} 

Lời giải thích đầy đủ về nguồn gốc có thể được tìm thấy trong bản thân liên kết :)